Min-heap

Prerequisites

• Binary tree basics.
• Arrays and index arithmetic.
• Logarithms.

The analogy

How it works

Start with heapify on paper

Heapify [3, 1, 4, 1, 5]: for each parent, from the last one (index 1) back to the root, let it sink below its smaller child while it is bigger. Predict, then open "Check".

Finish the picture: inserting and reading in order

Insert 0 into [1, 1, 4, 3, 5], then look at the level-order traversal.

• Insert 0 at index 5 (child of index 2). Predict how far it rises.
  Check

  0 < 4: swap, giving [1, 1, 0, 3, 5, 4]; 0 < 1 at the root: swap, giving [0, 1, 1, 3, 5, 4].

• Level-order traversal. Predict it without drawing the tree.
  Check

  It is just the array order: 0, 1, 1, 3, 5, 4. Note it isn't sorted: a heap only guarantees parent ≤ child.

The rule in plain words

Heap rule: every parent is ≤ its children; the tree is complete, filled level by level from the left, so it fits in an array.

Heapify: sift down each parent from index $\lfloor n/2 \rfloor - 1$ back to 0. Insert: append, then sift up.

The code

Read this code after you have done heapify by hand. It will make more sense.

void sift_down(int a[], int n, int i) {       /* min-heap version */
    for (;;) {
        int s = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] < a[s]) s = l;           /* s = smallest of the three */
        if (r < n && a[r] < a[s]) s = r;
        if (s == i) return;                        /* heap rule holds here */
        int t = a[i]; a[i] = a[s]; a[s] = t;
        i = s;
    }
}

void build_min_heap(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, n, i);   /* last parent to root */
}

graph TD
  A((1)) --> B((1))
  A --> C((4))
  B --> D((3))
  B --> E((5))
          

How fast is it?

In heapify, about $n/2^{h+1}$ nodes sit at height $h$ and each sinks at most $h$ levels. The total work is bounded by:

Insert and remove-min follow one path of a complete tree of height $\lfloor \log_2 n \rfloor$.

Common mistakes

• Building top-down by sifting down from index 0 first, which can leave lower subtrees unheaped.
• Swapping with the first smaller child instead of the smallest child.
• Thinking the heap array is sorted.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• The minimum is at the root because every parent is ≤ its children.
• A heap fits in an array because it is a complete tree, so children of $i$ are at $2i+1$ and $2i+2$.
• Heapify is $O(n)$ because half the nodes are leaves and most others sink only a level or two.
• Insert and remove-min are $O(\log n)$ because they move one value along one path of a short tree.
• Heapify goes bottom-up because sift-down needs both subtrees to be heaps already.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a min-heap like an org chart where managers earn less than their reports?
   Sample answer

   The rule only compares each person with their manager, yet it guarantees the lowest salary is at the very top.

2. Walk through heapifying [3, 1, 4, 1, 5].
   Sample answer

   Index 1 stays (no smaller child). The root 3 swaps with 1, then again with the other 1, giving [1, 1, 4, 3, 5].

3. Why does build_min_heap start at n / 2 - 1?

   A good answer says what the higher indices are.

   Sample answer

   Indices from n/2 upwards are leaves, which are already heaps of one node. The last node with a child is n/2 - 1.

4. So what is a min-heap, in one sentence?
   Sample answer

   A complete binary tree stored in an array where every parent is ≤ its children, so the minimum is at the root.

5. Why is heapify $O(n)$ rather than $O(n \log n)$?

   A good answer looks at where nodes are.

   Sample answer

   Half the nodes are leaves and don't move, a quarter sink at most one level, and so on. Only a handful near the top can sink far, so the sum is $O(n)$.

6. What do build, insert, remove-min and peek cost?
   Sample answer

   Build $O(n)$, insert and remove-min $O(\log n)$, peek $O(1)$.

7. Why is a heap not a sorted array, and when does that matter?
   Sample answer

   It only orders parents against children, so siblings and cousins can be in any order. You can't read the second-smallest from a fixed index or binary search it.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the $O(n)$ sum and the strict-comparison detail. I'd keep the org-chart analogy, heapifying [3, 1, 4, 1, 5], and "minimum at the root, $O(\log n)$ insert and remove".

External resources

• VisuAlgo: Binary heap: try "Create(A) - O(N)" to watch bottom-up heapify.
• GeeksforGeeks: Min-heap: operations with code.
• Wikipedia: Binary heap: the $O(n)$ build proof and array layout.
• Python docs: heapq: a real min-heap API.

Videos

• YouTube search: build heap in O(n): pick an explanation of bottom-up heapify.