🏔️ Heaps

The Tournament Bracket Analogy

In a tournament bracket:

• Winners move up to the next round
• The champion is at the top
• A parent is placed above the players it “beats”

A max-heap works like this: Each parent value is at least as large as its children. The root is the "champion" (the maximum value).

A min-heap is the opposite: Each parent value is at most as large as its children. The root is the minimum.

Heap Structure

It's a Complete Binary Tree

Max-Heap:
          90
        /    \
      80      70
     /  \    /  \
    50  60  65  40
   / \
  30  45

Properties:
1. Complete: fills left to right
2. Heap property: parent ≥ children (max-heap)

Stored as an Array

Array: [90, 80, 70, 50, 60, 65, 40, 30, 45]
Index:   0   1   2   3   4   5   6   7   8

For node at index i:
  Parent: (i - 1) / 2
  Left child: 2i + 1
  Right child: 2i + 2

No pointers needed! The structure is implicit.

Min-Heap vs Max-Heap

Max-Heap

          90          Parent ≥ Children
        /    \
      80      70
     /  \
    50  60

extractMax() → 90 (the root)
Largest is kept at the top (the root).

Min-Heap

          10          Parent ≤ Children
        /    \
      20      30
     /  \
    40  50

extractMin() → 10 (the root)
Smallest is kept at the top (the root).

Heap Operations

Insert: O(log n)

Add at the end, then "bubble up":

Insert 85 into max-heap:

1. Add at end:
          90
        /    \
      80      70
     /  \    /
    50  60  85

2. Bubble up (85 > 70):
          90
        /    \
      80      85
     /  \    /
    50  60  70

Keep swapping with parent until heap property restored.

Extract: O(log n)

Remove root, replace with last element, "bubble down":

Extract max (90):

1. Replace root with last:
          45
        /    \
      80      70
     /  \
    50  60

2. Bubble down (45 < 80):
          80
        /    \
      45      70
     /  \
    50  60

3. Continue (45 < 60):
          80
        /    \
      60      70
     /  \
    50  45

Peek: O(1)

Just look at the root - no changes needed.

Heapify: O(n)

Build a heap from an unsorted array in linear time by bubbling down from bottom up.

Time Complexities

Where Heaps Are Used

1. Priority Queues

Heaps are a common implementation for priority queues:

Tasks with priorities:
  Insert task with priority → O(log n)
  Get highest priority task → O(log n)

2. Dijkstra's Algorithm

Finding shortest paths:

Typically process the node with the smallest known distance next.
Min-heap gives this in O(log n)!

3. K Largest/Smallest Elements

Find 3 largest from stream:
Keep min-heap of size 3.
If new element > heap top, replace.

Heap tends to contain the 3 largest seen so far.
Heap tends to contain the 3 largest seen so far.

4. Median Finding

Use two heaps:
  Max-heap for smaller half
  Min-heap for larger half

Median = average of the two tops (or just max-heap top)

5. Heap Sort

1. Build max-heap from array: O(n)
2. Repeatedly extract max and place at end: O(n log n)

Total: O(n log n), in-place sorting!

Classic Heap Problems

1. Kth Largest Element

Array: [3, 2, 1, 5, 6, 4], k = 2

Min-heap of size k:
  Process 3, 2, 1: heap = [2, 3, 1] → keep size k=2: [2, 3]
  Process 5: 5 > 2, replace → [3, 5]
  Process 6: 6 > 3, replace → [5, 6]
  Process 4: 4 < 5, skip

Top of heap = 5 = 2nd largest ✓

2. Merge K Sorted Lists

3 sorted lists: [1,4,7], [2,5,8], [3,6,9]

Min-heap holds smallest from each list:
  Heap: [(1, list1), (2, list2), (3, list3)]

Extract 1, add next from list1:
  Heap: [(2, list2), (3, list3), (4, list1)]

Repeat to get: [1, 2, 3, 4, 5, 6, 7, 8, 9]

3. Top K Frequent Elements

Array: [1,1,1,2,2,3], k = 2

1. Count frequencies: {1:3, 2:2, 3:1}
2. Use min-heap of size k by frequency
3. Result: [1, 2] (most frequent)

Heap vs BST

Use a heap when you mainly need min or max, not arbitrary search.

Common Mistakes

1. Confusing Min and Max Heap

Min-heap: smallest at root. Max-heap: largest at root. Most libraries default to min-heap!

2. Heap is NOT Sorted

Max-heap: [90, 80, 70, 50, 60]
This is NOT fully sorted!
It just guarantees parent ≥ children.
It maintains the heap property (parent ≥ children).

3. Wrong Index Calculation

Remember 0-indexed formulas:

• Parent: (i - 1) / 2
• Left child: 2i + 1
• Right child: 2i + 2

4. Forgetting Heapify After Changes

After changing an element, you generally need to restore the heap property. After changing an element, you generally need to restore the heap property.

FAQ

Q: Why is building a heap O(n), not O(n log n)?

Most nodes are near the bottom and need minimal bubbling. The math works out to O(n).

Q: When should I use a heap vs sorted array?

Heap: frequent inserts and extracts. Sorted array: many searches, few modifications.

Q: Max-heap in Python?

Python's heapq is min-heap. For max-heap, negate values: Insert -x, extract gives -max, negate back.

Q: Is heap sort better than quicksort?

Heap sort has predictable O(n log n) behavior; quicksort is often fast in practice, but it depends on the input and implementation.

Summary

A heap is a complete binary tree where parent compares consistently to children (larger for max-heap, smaller for min-heap).

Key Takeaways:

• Min-heap: smallest at root; Max-heap: largest at root
• Stored as array, no pointers needed
• Insert/Extract: O(log n); Peek: O(1); Build: O(n)
• Foundation for priority queues
• Used in: Dijkstra, K largest/smallest, median finding
• Not fully sorted - maintains a parent-child relationship

Heaps efficiently answer "what's the highest priority right now?" queries!