Max-heap

Prerequisites

• Min-heap: the same idea with the comparison flipped.
• Array indices: children of $i$ at $2i+1$ and $2i+2$.
• Logarithms.

The analogy

How it works

Start with heapify on paper

Heapify [3, 1, 4, 1, 5] into a max-heap: from the last parent back to the root, sink each node below its bigger child while it is smaller. Predict, then open "Check".

Finish the picture: insert and remove the maximum

Work on [5, 3, 4, 1, 1].

• Insert 6 at index 5 (child of index 2). Predict where it ends.
  Check

  6 > 4: swap → [5, 3, 6, 1, 1, 4]; 6 > 5: swap → [6, 3, 5, 1, 1, 4]. It's the new root.

• Remove the max. Predict the heap afterwards.
  Check

  Return 6; the last leaf 4 goes to the root: [4, 3, 5, 1, 1]; 4 < 5, swap: [5, 3, 4, 1, 1].

The rule in plain words

Heap rule: every parent is ≥ its children, in a complete tree stored in an array.

Insert: append, then sift up while bigger than the parent. Remove max: move the last leaf to the root, then sift down below the bigger child.

The code

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

typedef struct { int a[100]; int n; } MaxHeap;

void max_insert(MaxHeap *h, int v) {                 /* caller checks n < 100 */
    int i = h->n++;
    h->a[i] = v;
    while (i > 0 && h->a[(i - 1) / 2] < h->a[i]) {   /* parent smaller: swap up */
        int p = (i - 1) / 2, t = h->a[p];
        h->a[p] = h->a[i]; h->a[i] = t;
        i = p;
    }
}

void max_sift_down(int a[], int n, int i) {
    for (;;) {
        int b = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[b]) b = l;            /* b = biggest of the three */
        if (r < n && a[r] > a[b]) b = r;
        if (b == i) return;
        int t = a[i]; a[i] = a[b]; a[b] = t;
        i = b;
    }
}

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

How fast is it?

Finding the $k$ largest values: build a max-heap once, then remove the max $k$ times:

For a small $k$ this beats sorting everything, which costs $O(n \log n)$.

Common mistakes

• Swapping with the smaller child when sifting down a max-heap.
• Comparing with > where < belongs in the sift-up loop: a parent smaller than the new value must move down.
• Assuming the second-largest value is always at index 1; it can be at index 2.

Try it yourself

Did you know?

Key points to remember

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

• The maximum is at the root because every parent is ≥ its children.
• Sinking swaps with the bigger child because that child is the only safe new parent.
• Insert and remove-max are $O(\log n)$ because the complete tree has height $\lfloor \log_2 n \rfloor$.
• Top-$k$ costs $O(n + k \log n)$ because building is linear and each removal is logarithmic.
• Heap sort uses a max-heap because each removed maximum goes into its final place at the end of the array.

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 max-heap like a ranked tournament bracket?
   Sample answer

   Every team is ranked above the teams feeding into it, so the best team is always at the top.

2. Walk through heapifying [3, 1, 4, 1, 5] into a max-heap.
   Sample answer

   Index 1 (1) swaps with 5, giving [3, 5, 4, 1, 1]; the root 3 swaps with 5, giving [5, 3, 4, 1, 1]; 3 then stays above two 1s.

3. Why does max_insert loop while the parent is smaller than the new value?

   A good answer states the rule being repaired.

   Sample answer

   The rule is parent ≥ child. A smaller parent violates it, so they swap and the check repeats one level higher.

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

   A complete binary tree in an array where every parent is ≥ its children, so the maximum is at the root.

5. Why must a sinking node swap with the bigger child?

   A good answer tries the smaller child.

   Sample answer

   If it swapped with the smaller child, that child would become the parent of the bigger one, breaking the rule. The bigger child is ≥ everything below it.

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

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

7. When is a max-heap better than sorting for "the 10 largest values"?
   Sample answer

   When $n$ is large: building is $O(n)$ and 10 removals cost $O(10 \log n)$, much less than sorting in $O(n \log n)$.

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 top-$k$ and the negation trick. I'd keep the tournament analogy, heapifying [3, 1, 4, 1, 5] into [5, 3, 4, 1, 1], and "max at the root, $O(\log n)$ insert and remove".

External resources

• VisuAlgo: Binary heap: a max-heap by default: insert and extract-max step by step.
• GeeksforGeeks: Max-heap: operations with code.
• Wikipedia: Heap: variants and applications.

Videos

• YouTube search: max heap insert and delete: pick a short walkthrough.