Min Heap vs Max Heap When to Use Which in DSA Go - Trade-offs & Analysis

Mental Model

A min heap always keeps the smallest item on top, while a max heap keeps the largest item on top. This helps quickly find the smallest or largest value.

Analogy: Think of a min heap like a line where the shortest person is always at the front, and a max heap like a line where the tallest person is always at the front.

Min Heap:
       [1]
      /   \
    [3]   [5]
   /  \
 [7]  [9]

Max Heap:
       [9]
      /   \
    [5]   [3]
   /  \
 [1]  [2]

Dry Run Walkthrough

Input: Min heap with elements: 5, 3, 9, 1, 7; Max heap with elements: 1, 3, 5, 7, 9

Goal: Show how min heap keeps smallest on top and max heap keeps largest on top after inserting elements

Step 1: Insert 5 into empty min heap

Min Heap: [5]
Max Heap: []

Why: Start building min heap with first element

Step 2: Insert 3 into min heap, bubble up to keep smallest on top

Min Heap: [3] -> [5]
Max Heap: []

Why: 3 is smaller than 5, so it moves up to root

Step 3: Insert 9 into min heap, stays as child since larger

Min Heap: [3] -> [5], [9]
Max Heap: []

Why: 9 is larger than 3, no bubble up needed

Step 4: Insert 1 into min heap, bubble up to root

Min Heap: [1] -> [3], [9], [5]
Max Heap: []

Why: 1 is smallest, so it moves to root

Step 5: Insert 7 into min heap, stays as child

Min Heap: [1] -> [3], [9], [5], [7]
Max Heap: []

Why: 7 is larger than 1, no bubble up

Step 6: Insert 1,3,5,7,9 into empty max heap one by one, bubbling up largest to root

Max Heap: [9] -> [7], [5], [1], [3]

Why: 9 is largest, so it moves to root

Result:

Min Heap final: 1 -> 3 -> 9 -> 5 -> 7
Max Heap final: 9 -> 7 -> 5 -> 1 -> 3

Annotated Code

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

// An IntHeap is a min-heap of ints.
type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

// MaxHeap is a max-heap of ints.
type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func main() {
	minH := &MinHeap{}
	heap.Init(minH)
	for _, v := range []int{5, 3, 9, 1, 7} {
		heap.Push(minH, v) // insert and bubble up
	}
	fmt.Print("Min Heap final: ")
	for _, v := range *minH {
		fmt.Printf("%d -> ", v)
	}
	fmt.Println("null")

	maxH := &MaxHeap{}
	heap.Init(maxH)
	for _, v := range []int{1, 3, 5, 7, 9} {
		heap.Push(maxH, v) // insert and bubble up
	}
	fmt.Print("Max Heap final: ")
	for _, v := range *maxH {
		fmt.Printf("%d -> ", v)
	}
	fmt.Println("null")
}

heap.Push(minH, v) // insert and bubble up

insert element and bubble up to maintain min heap property

heap.Push(maxH, v) // insert and bubble up

insert element and bubble up to maintain max heap property

Output

Min Heap final: 1 -> 3 -> 9 -> 5 -> 7 -> null

Max Heap final: 9 -> 7 -> 5 -> 1 -> 3 -> null

Complexity Analysis

Time: O(n log n) because each insertion takes O(log n) and we insert n elements

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

vs Alternative: Using a sorted array would take O(n) per insertion, so heap is faster for dynamic data

Edge Cases

empty heap

heap initializes empty and can accept insertions

DSA Go

heap.Init(minH)

single element

heap has one element which is both min and max

DSA Go

heap.Push(minH, v)

all elements equal

heap keeps all elements but order does not matter as all are same

DSA Go

heap.Push(minH, v)

When to Use This Pattern

When you need quick access to smallest or largest element repeatedly, use min heap or max heap respectively because they keep that element at the top efficiently.

Common Mistakes

Mistake: Using min heap when you need largest element quickly
Fix: Use max heap instead to keep largest element on top

Mistake: Not bubbling up after insertion
Fix: Always bubble up to restore heap property after insert

Summary

Min heap keeps smallest element on top; max heap keeps largest element on top.

Use min heap when you want quick access to smallest item, max heap for largest item.

The key is that heap structure keeps the top element as min or max by bubbling up on insert.