Heap operations — insert O(log n), extract-max - min O(log n), decrease-key: Visual walkthrough

Before any symbol appears, three words in plain English:

Step 1 — An array is secretly a tree

WHY this rule and not another. We want a tree with no pointers (pointers waste memory and cache). The only way to fake a tree inside a flat array is a fixed arithmetic recipe that turns "where is my child?" into a calculation. Doubling-plus-one is that recipe, and it works because a complete tree fills level by level with no gaps, so positions never skip.

PICTURE. Look at the figure: the same five numbers appear once as a row of slots (bottom) and once stacked as a tree (top). The colored arrows show slot $0$ pointing to slots $1$ and $2$ ; slot $1$ pointing to slots $3$ and $4$ .

Figure — Heap operations — insert O(log n), extract-max - min O(log n), decrease-key

Step 2 — The one promise the tree keeps

WHY only this weak rule. A fully sorted structure is expensive to maintain. We ask for the weakest thing that still puts the champion on top: if every parent beats its children, then by following "bigger, bigger, bigger" upward you always reach the single biggest number — the root. That is all we need to read the max instantly.

PICTURE. Green check-arrows run down every parent→child link where " $\geq$ " holds. The red dashed link between the two children $30$ and $20$ has a big "no rule here" cross — siblings are unordered.

Step 3 — Reading the max is free; the trouble begins when we remove it

WHY we cannot just shift everyone up. The obvious idea — slide the whole array left by one — touches all $n$ boxes, that is $O (n)$ , too slow. We need a fix that disturbs almost nothing.

PICTURE. The root $40$ is lifted out (shown floating away, "returned to caller"). A red hole sits at slot $0$ . The array below shows the hole too.

Step 4 — Plug the hole with the LAST leaf (the cheap move)

WHY the last leaf specifically. Completeness says "the last level fills left to right, no gaps." The only box we can delete without leaving a gap is the very last one. Moving it to the top keeps the tree perfectly complete for the price of one move — no shifting, no hole in the middle.

PICTURE. An arrow carries $5$ from the last leaf up to the root. The old last slot fades out (size shrinks from $5$ to $4$ ). The tree is complete again — but $5$ at the top is obviously too small: red warning marks sit on both links from the new root.

Step 5 — Sift-down, move 1: swap with the bigger child

WHY the larger child, not just any bigger one. After the swap the promoted child becomes the new parent of the other child. If we promoted the smaller one, it might still be beaten by its sibling and the property would stay broken. Promoting the maximum of the two guarantees the new parent dominates both below it in one shot.

PICTURE. Three boxes are outlined: root $5$ and children $30$ , $20$ . The larger child $30$ glows; a curved swap-arrow exchanges $5$ and $30$ . The intruder $5$ is now one level lower.

Step 6 — Sift-down, move 2: the intruder hits the bottom

WHY it must stop soon. Every swap pushes the intruder down exactly one level. A tree of $n$ boxes has height $⌊ lo g_{2} n ⌋$ , so the intruder can fall at most that many times. That is the whole $O (lo g n)$ argument — we walked one root-to-leaf path, nothing more.

PICTURE. The path the intruder $5$ travelled is highlighted as a single glowing chain from root to leaf. Every box off that path is greyed out — untouched — visually proving "only one path was disturbed."

Recall Degenerate cases — do they break the walk?

One-element heap, extract-max? ::: Return $A [0]$ ; array becomes empty; sift-down has no children so stops instantly. $O (1)$ , still fine. Node with only a LEFT child (last level half-full)? ::: Compare with the one child only; the right-child slot is out of range, so treat it as $- \infty$ . This is exactly Step 6. What if the last leaf we promote is already the biggest remaining? ::: Then no child beats it, sift-down does zero swaps, cost is $O (1)$ — the worst case is $lo g n$ , not every case.

Step 7 — Why the height is $lo g_{2} n$ (the cost, finally nailed)

WHY that gives a log. To hold $n$ boxes across $h + 1$ levels you need $1 + 2 + 4 + \dots + 2^{h} = 2^{h + 1} - 1 \geq n$ , so $h \approx lo g_{2} n$ . Doubling each step is exactly what " $lo g$ " measures — how many doublings to reach $n$ .

PICTURE. A bar chart of boxes-per-level ( $1, 2, 4, 8, \dots$ ) beside the tree, with a bracket labelling the height as " $lo g_{2} n$ levels", and a red arrow tracing the single sift-down path spanning that height.

The one-picture summary

The final figure stacks the whole story on one canvas: (1) array→tree seating, (2) the max lifted out, (3) last leaf plugged into the top, (4→5) the single highlighted path the intruder sinks along, and (6) the height bracket labelled $lo g_{2} n$ — the reason the whole thing is cheap.

Recall Feynman: tell the whole walkthrough to a 12-year-old

Imagine a pyramid of boxes where every box holds a bigger number than the two boxes hanging below it — so the biggest number is always on top and you can read it in a blink. Now you want to take the top box away. You lift it out and there's an empty spot up top. Sliding everyone over would take forever, so instead you grab the very last little box in the bottom-right corner (the only one you can remove without leaving a gap) and plop it on top. It's probably too small to be king, so you let it sink: at each level you look at its two kids, swap it with the bigger kid, and repeat. It stops the moment it's bigger than both kids or reaches the bottom. Because the pyramid doubles its width every level, it only has about $lo g_{2} n$ levels tall — so the little box can only sink that few times. One path down, and you're done. That's why removing the biggest costs $O (lo g n)$ , and the same "sink or climb one path" idea powers insert, decrease-key, and priority queues used in Dijkstra and Prim.

Related: Complete Binary Tree · Build-Heap (Heapify) · Heapsort · Binary Search Tree.