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.

Practice

1. What is the main property of a max-heap data structure?

easy

A. Every parent node is less than or equal to its children

B. Every parent node is greater than or equal to its children

C. All leaf nodes are at the same level

D. The tree is always a complete binary tree

Solution

1. Step 1: Understand max-heap property

   A max-heap requires that each parent node is greater than or equal to its children nodes.

2. Step 2: Compare options with max-heap definition

   Every parent node is greater than or equal to its children matches the max-heap property exactly. Every parent node is less than or equal to its children describes a min-heap. All leaf nodes are at the same level and D are about tree shape, not heap order.

3. Final Answer:

   Every parent node is greater than or equal to its children -> Option B

4. Quick Check:

   Max-heap property = parent ≥ children [OK]

Hint: Max-heap means parent ≥ children always [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking heap requires all leaves at same level
• Mixing heap order with tree completeness

2. Which of the following is the correct way to declare a min-heap using Go's container/heap package?

easy

A. var h []int = make([]int, 0) // slice for heap

B. var h heap.Interface = []int{} // direct slice assignment

C. var h = heap.NewMinHeap() // built-in min heap constructor

D. var h heap.Interface = &IntHeap{} // IntHeap implements heap.Interface

Solution

1. Step 1: Recall Go heap package usage

   Go's container/heap requires a type implementing heap.Interface, like IntHeap struct.

2. Step 2: Analyze options for correct syntax

   var h heap.Interface = &IntHeap{} // IntHeap implements heap.Interface correctly declares a heap.Interface variable with a pointer to IntHeap. var h []int = make([]int, 0) // slice for heap is just a slice, not a heap. var h = heap.NewMinHeap() // built-in min heap constructor is invalid; no NewMinHeap exists. var h heap.Interface = []int{} // direct slice assignment assigns a slice directly to heap.Interface, which is invalid.

3. Final Answer:

   var h heap.Interface = &IntHeap{} // IntHeap implements heap.Interface -> Option D

4. Quick Check:

   Heap needs heap.Interface implementation [OK]

Hint: Heap in Go needs heap.Interface implementation [OK]

Common Mistakes:

• Using slice directly without implementing heap.Interface
• Assuming built-in heap constructors exist
• Assigning slice to heap.Interface without pointer

3. Consider the following Go code using a max-heap implemented with container/heap:

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{3, 1, 4}
    heap.Init(h)
    heap.Push(h, 2)
    max := heap.Pop(h)
    fmt.Println(max)
}

What is the printed output?

medium

A. 4

B. 3

C. 2

D. 1

Solution

1. Step 1: Understand heap initialization and ordering

   The IntHeap Less method uses h[i] > h[j], so it is a max-heap. Initial elements are 3,1,4.

2. Step 2: Trace heap operations

   After heap.Init, the heap orders elements as max-heap. Then 2 is pushed. The heap now contains 4,3,1,2. heap.Pop removes the max element, which is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Max-heap pop returns max = 4 [OK]

Hint: Max-heap pop returns largest element [OK]

Common Mistakes:

• Confusing min-heap and max-heap Less function
• Assuming heap.Pop returns smallest element
• Not tracing heap.Init effect on order

4. The following Go code attempts to create a min-heap but has a bug:

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{5, 3, 8}
    heap.Init(h)
    heap.Push(h, 1)
    min := heap.Pop(h)
    fmt.Println(min)
}

What is the bug and how to fix it?

medium

A. Less method uses > instead of <; change to h[i] < h[j]

B. Push method should use pointer receiver; change to (h IntHeap)

C. Pop method returns wrong element; should return old[0]

D. Heap must be initialized with make([]int, 0) instead of literal

Solution

1. Step 1: Identify heap type from Less method

   The Less method uses h[i] > h[j], which creates a max-heap, not a min-heap.

2. Step 2: Fix Less method for min-heap

   To make a min-heap, Less should return h[i] < h[j]. This fixes the ordering so smallest element is on top.

3. Final Answer:

   Less method uses > instead of <; change to h[i] < h[j] -> Option A

4. Quick Check:

   Min-heap requires Less = h[i] < h[j] [OK]

Hint: Min-heap Less returns h[i] < h[j] [OK]

Common Mistakes:

• Confusing Less method direction for min vs max heap
• Changing Push receiver incorrectly
• Misunderstanding Pop return value

5. You have a list of integers: [7, 2, 5, 3, 9, 1]. You want to find the 3 largest elements efficiently using a min-heap of size 3. Which approach correctly uses heap properties to solve this?

hard

A. Sort the list and pick last 3 elements

B. Build a max-heap with all elements, then pop 3 times to get largest elements

C. Build a min-heap with first 3 elements, then for each remaining element, if greater than heap root, replace root and heapify

D. Build a min-heap with all elements and pop 3 times

Solution

1. Step 1: Understand problem and heap size constraint

   We want top 3 largest elements efficiently, so keep a min-heap of size 3 to track current largest.

2. Step 2: Use min-heap to track largest elements

   Build min-heap with first 3 elements. For each remaining element, if it is larger than heap root (smallest in heap), replace root and heapify. This keeps 3 largest elements in heap.

3. Step 3: Analyze options

   Build a min-heap with first 3 elements, then for each remaining element, if greater than heap root, replace root and heapify matches this approach. Build a max-heap with all elements, then pop 3 times to get largest elements uses max-heap on all elements, which is less efficient. Sort the list and pick last 3 elements sorts entire list, which is more work. Build a min-heap with all elements and pop 3 times pops smallest elements, not largest.

4. Final Answer:

   Build a min-heap with first 3 elements, then for each remaining element, if greater than heap root, replace root and heapify -> Option C

5. Quick Check:

   Min-heap size 3 tracks top 3 largest [OK]

Hint: Use min-heap of size k to track k largest elements [OK]

Common Mistakes:

• Using max-heap on all elements (less efficient)
• Sorting entire list unnecessarily
• Using min-heap on all elements and popping smallest