Heap Concept Structure and Properties in DSA Go

Mental Model

A heap is a special tree where the biggest or smallest value is always at the top, making it easy to find quickly.

Analogy: Imagine a pile of boxes stacked so that the heaviest box is always on top, so you can grab it without moving others.

       10
      /  \
     5    3
    / \  / \
   2  4 1 null

Dry Run Walkthrough

Input: array: [10, 5, 3, 2, 4, 1]

Goal: Show how the heap keeps the largest number at the top and maintains order after adding elements

Step 1: Start with empty heap and insert 10

10

Why: First element becomes the root, so it is the biggest by default

Step 2: Insert 5, place as left child of 10

    10
   /  \
  5  null

Why: New element goes to next available spot, no need to swap since 10 > 5

Step 3: Insert 3, place as right child of 10

    10
   /  \
  5    3

Why: 3 is smaller than 10, so heap property holds

Step 4: Insert 2, place as left child of 5

      10
     /  \
    5    3
   / 
  2  null

Why: 2 is smaller than 5, so no swaps needed

Step 5: Insert 4, place as right child of 5

      10
     /  \
    5    3
   / \  
  2   4

Why: 4 is smaller than 5, heap property still holds

Step 6: Insert 1, place as left child of 3

      10
     /  \
    5    3
   / \  / \
  2  4 1 null

Why: 1 is smaller than 3, so heap property is maintained

Result:

      10
     /  \
    5    3
   / \  / \
  2  4 1 null
Largest value 10 is at the top, heap property holds

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Heap struct {
	data []int
}

func (h *Heap) Insert(val int) {
	h.data = append(h.data, val) // add new value at the end
	h.heapifyUp(len(h.data) - 1) // fix heap from bottom up
}

func (h *Heap) heapifyUp(index int) {
	for index > 0 {
		parent := (index - 1) / 2
		if h.data[parent] >= h.data[index] {
			break // heap property satisfied
		}
		h.data[parent], h.data[index] = h.data[index], h.data[parent] // swap
		index = parent // move up to parent
	}
}

func (h *Heap) Print() {
	for i, v := range h.data {
		fmt.Printf("[%d]=%d ", i, v)
	}
	fmt.Println()
}

func main() {
	h := &Heap{}
	inputs := []int{10, 5, 3, 2, 4, 1}
	for _, v := range inputs {
		h.Insert(v)
	}
	h.Print()
}

h.data = append(h.data, val) // add new value at the end

append new element at the bottom of the heap

h.heapifyUp(len(h.data) - 1) // fix heap from bottom up

restore heap property by moving new element up if needed

parent := (index - 1) / 2

find parent index to compare with current node

if h.data[parent] >= h.data[index] { break }

stop if parent is bigger or equal, heap property holds

h.data[parent], h.data[index] = h.data[index], h.data[parent]

swap child with parent to fix heap order

index = parent

move index up to continue checking heap property

Output

[0]=10 [1]=5 [2]=3 [3]=2 [4]=4 [5]=1 

Complexity Analysis

Time: O(log n) because each insertion may move the new element up the tree height

Space: O(n) because we store all elements in an array representing the heap

vs Alternative: Compared to sorting after each insertion (O(n log n)), heap insertion is faster for maintaining order

Edge Cases

empty heap

inserting first element sets it as root without swaps

DSA Go

if h.data[parent] >= h.data[index] { break }

inserting duplicate values

duplicates are allowed and placed according to heap rules

DSA Go

if h.data[parent] >= h.data[index] { break }

When to Use This Pattern

When you need quick access to the largest or smallest item and fast insertions, use a heap because it keeps the top element always ready.

Common Mistakes

Mistake: Not swapping child and parent when child is bigger, breaking heap property
Fix: Add swap logic in heapifyUp to restore heap order after insertion

Mistake: Using a linked structure instead of array, complicating index calculations
Fix: Use array representation for simpler parent/child index math

Summary

A heap is a tree structure that keeps the largest (or smallest) element at the top for quick access.

Use a heap when you want to efficiently find and remove the max or min value repeatedly.

The key is to keep the tree balanced and swap elements up or down to maintain the heap property.