Worked examples — Heap sort — O(n log n), in-place, not stable

This page is a drill floor. We take the heap sort machine and run it against every kind of input it will ever meet — so no test case can surprise you. If a word below feels unfamiliar, the parent note defines it; here we only use it, slowly.

The scenario matrix

Before working examples, let's list every class of situation heap sort can face. Each later example is tagged with the cell(s) it covers.

We now cover A–I with 8 worked examples.

Example 1 — Cell C (typical jumble): full trace

Forecast first: guess — will the first thing that happens be a swap, or a build? (The array is not a heap yet, so we must build first. Pause and predict where 10 ends up.)

We index the array as a tree. Node $i$'s children live at $2i+1$ and $2i+2$.

Figure 1 — raw array as a tree (before build):

Phase 1 — Build the heap. We call sift_down on the last internal (non-leaf) node down to the root. The last internal node index is $\lfloor n/2\rfloor -1=\lfloor 5/2\rfloor -1=1$.

1. sift_down(A, 1, 5) — node $1$ holds 10, children at indices $3,4$ = 5,1. Why this step? Leaves (indices $2,3,4$) are already trivially heaps; we start at the deepest parent so its subtrees are settled before we touch it. Largest of $\{10,5,1\}$ is 10, already on top → no swap.
2. sift_down(A, 0, 5) — node $0$ holds 4, children 10 (idx 1) and 3 (idx 2). Why this step? Move up one internal node; its children subtrees are now valid heaps, so a single sift fixes it. 10 > 4 → swap. Array becomes [10, 4, 3, 5, 1]. Now $i=1$: node 4, children 5,1. 5>4 → swap → [10, 5, 3, 4, 1]. $i=3$ is a leaf → stop.

Heap built: [10, 5, 3, 4, 1].

Figure 2 — the built max-heap (champion on top):

Phase 2 — Sort-down. Repeat the crown-and-shrink move: swap root to the back, shrink the live region, re-heapify the new root. Each numbered step below states its own purpose.

3. end=4: crown → swap idx $0,4$ → [1, 5, 3, 4, | 10]. sift_down(A,0,4): 1 vs 5,3 → swap 5; then 1 vs child 4 (idx3) → swap → [5, 4, 3, 1, | 10]. Why this step? The root 10 was the global max, so it belongs in the last live slot — crowning freezes it there permanently. But the tiny 1 we dragged to the root breaks the heap property, so sift_down(A,0,4) (live region size $4$) pushes it back down to restore a valid heap for the next round.
4. end=3: crown → swap idx $0,3$ → [1, 4, 3, | 5, 10]. sift_down(A,0,3): 1 vs 4,3 → swap 4 → [4, 1, 3, | 5, 10]. Why this step? The current root 5 is the max of the shrunken heap, so it is frozen just left of 10. The demoted 1 again violates the heap, so we sift over live size $3$ to re-expose the next champion.
5. end=2: crown → swap idx $0,2$ → [3, 1, | 4, 5, 10]. sift_down(A,0,2): 3 vs 1 → no swap. Why this step? Crown 4 into place; the new root 3 already dominates its single child 1, so sift over live size $2$ finds nothing to do — that is the correct outcome, not a skipped step.
6. end=1: crown → swap idx $0,1$ → [1, | 3, 4, 5, 10]. Done. Why this step? One live pair remains; crowning the larger to the back leaves a single element A[0], which is a valid heap by itself — so the loop stops (it runs only down to end = 1).

Result: [1, 3, 4, 5, 10].

Why build is only $O(n)$ — the height-weighted count

Example 2 — Cell A (already sorted ascending)

Forecast: many beginners guess "already sorted = instant." Wrong for heap sort — an ascending array is the worst shape for a max-heap because the biggest value sits at the far end, not the top.

1. sift_down(A,1,5) — node 2 (idx 1), children 4,5 → largest 5 → swap → [1,5,3,4,2]. Why this step? We start at the deepest internal node so its subtrees (pure leaves) are already valid before we fix it; the big leaf 5 must rise to be a legal parent.
2. sift_down(A,0,5) — node 1 (idx 0), children 5,3 → swap 5 → [5,1,3,4,2]; then 1 at idx 1, children 4,2 → swap 4 → [5,4,3,1,2]. Why this step? Now the two subtrees are valid heaps, so a single top-node sift settles the root; note 1 had to fall two levels, which is exactly why ascending input costs real work.
3. Sort-down (compressed): [5,4,3,1,2] → crown 5 → [4,2,3,1|5] → crown 4 → [3,2,1|4,5] → crown 3 → [2,1|3,4,5] → crown 2 → [1|2,3,4,5]. Why this step? Same crown-and-shrink loop as Example 1: each crown freezes the current max at the right end of the live region, then a sift restores the heap for the next crown.

Result: [1,2,3,4,5].

Example 3 — Cell B (reverse sorted)

Forecast: a descending array is already a valid max-heap (each parent $\ge$ children). So build does zero swaps — but sort-down still runs fully.

1. Build. sift_down(A,1,5): node 4, children 2,1 → largest 4 → no swap. sift_down(A,0,5): node 5, children 4,3 → no swap. Why this step? Confirms the array satisfies the heap property untouched — a genuine best case for Phase 1 only.
2. Sort-down unfolds exactly like Example 1's phase 2, ending sorted.

Result: [1,2,3,4,5].

Example 4 — Cell D (duplicates) + demonstrating not stable

Forecast: stable means equal keys keep their original order. Predict whether the two 3s come out a,b or b,a.

Keys only: [3, 3, 1], tag each: 3a, 3b, 1c.

1. Build, $n=3$. Last internal node $=\lfloor 3/2\rfloor -1=0$. sift_down(A,0,3): node 3a, children 3b (idx1), 1c (idx2). Comparison uses strict >; 3b > 3a is false, so largest stays $0$ → no swap. Heap: [3a, 3b, 1c]. Why this step? Ties don't trigger a swap here, so it looks safe... watch what sort-down does.
2. Sort-down, crown #1. end=2: crown → swap idx $0,2$ → [1c, 3b, | 3a]. Why this step? The champion 3a is now exiled to the back; but to reach the back it leapt over 3b, and this is precisely the move that can reorder equal keys. Now re-heapify the live region: sift_down(A,0,2): 1c vs child 3b → 3b > 1c → swap → [3b, 1c, | 3a]. Why re-heapify here? After crowning, the new root 1c is a leftover small value; sift-down restores the heap property so the next crown again pulls the true max.
3. Sort-down, crown #2. end=1: crown → swap idx $0,1$ → [1c, | 3b, 3a]. Why this step? One more crown finishes the array; no sift needed because a single-element live region is already a heap.

Result order: 1c, 3b, 3a → the two equal 3s came out b before a, reversing their input order.

Example 5 — Cells E & F (degenerate: empty, singleton, all-equal)

Forecast: which loops even execute? Predict the number of swaps for each.

(i) A = [], $n=0$. Build loop for i = n//2 - 1 down to 0 = for i = -1 down to 0 → runs zero times. Sort-down for end = n-1 down to 1 = for end = -1 down to 1 → zero times. Why this matters: the code must simply do nothing — no index $-1$ access, no crash. Result: [].

(ii) A = [7], $n=1$. Build: for i = -1..0 → skip. Sort-down: for end = 0 down to 1 → skip. Result: [7] — a one-element array is already sorted, and heap sort correctly touches nothing.

(iii) A = [9,9,9,9], $n=4$. Every comparison is 9 > 9 = false → sift_down never swaps.

• Build: nodes $1,0$ sifted, no swaps. Array unchanged.
• Sort-down: end=3: crown → swap idx $0,3$ (still 9,9, harmless) → sift, no swap. Same for end=2,1. Result: [9,9,9,9]. Crown swaps still happen (the crown always fires) but they move equal values, so the array looks unchanged.

Example 6 — Cell G (negative & mixed signs)

Forecast: the only operation is >. Since 7 > -5 and 0 > -2 behave normally, signs need no special handling — but let's confirm -5 (the most negative) ends up first.

1. Build, $n=5$, last internal $=1$. sift_down(A,1,5): node 7, children 0,3 → 7 largest → no swap. sift_down(A,0,5): node -2, children 7(idx1), -5(idx2) → swap 7 → [7,-2,-5,0,3]; then -2 at idx1, children 0,3 → largest 3 → swap → [7,3,-5,0,-2]. Why this step? Confirms > orders negatives correctly; -5 sinks toward the leaves, 7 rises to the root.
2. Sort-down. [7,3,-5,0,-2] → crown 7 → [3,0,-5,-2|7] → crown 3 → [0,-2,-5|3,7] → crown 0 → [-2,-5|0,3,7] → crown -2 → [-5|-2,0,3,7].

Result: [-5,-2,0,3,7]. The most-negative value -5 is correctly first, 0 sits between negatives and positives.

Example 7 — Cell H (word problem: live leaderboard top-3)

Forecast: heap sort crowns the max first. So the first three crowned elements ARE the top 3 — we can stop early after 3 crownings.

1. Build max-heap of all 7 scores. sift_down from index $\lfloor 7/2\rfloor -1=2$ up to $0$. After building, the root is the global max 91. Why this step? Building costs $O(n)$ and guarantees index $0$ = current maximum, exactly what a leaderboard needs.
2. Crown once: swap root 91 to the back → 1st place = 91. Re-heapify remaining 6; new root = 88.
3. Crown again: → 2nd place = 88. Re-heapify 5; new root = 63.
4. Crown again: → 3rd place = 63. Stop — we needed only 3 crownings, not a full sort. Why stop? Each crowning is a $\log n$ sift. Top-$k$ costs $O(n+k\log n)$ — cheaper than sorting all 7 when $k$ is small.

Result: top 3 = [91, 88, 63].

Example 8 — Cell I (exam twist: count crown swaps + min-heap flip)

Forecast: (a) is a counting argument, not a trace. (b) tests whether you understand why max-heap gives ascending order.

(a) Why reason, not trace? The sort-down loop is for end = n-1 down to 1, which runs exactly $n-1$ times, and each iteration performs exactly one crown swap. For $n=5$: $n-1=4$ crown swaps — no more, no less, regardless of the data. Answer (a): 4 crown swaps. (Sift-down inside may do extra swaps, but the crown count is fixed at $n-1$.)

(b) First, a reminder of the notation inside sift_down: l is the left-child index $2i+1$ and r is the right-child index $2i+2$ of the current node $i$; largest holds the index of the biggest value seen so far among the node and its two children. A max-heap keeps the largest on top by testing A[l] > A[largest] and A[r] > A[largest]; it sends the largest to the end, building ascending order left-to-right.

To get descending output, use a min-heap: track a variable smallest instead of largest, and flip both comparisons from A[l] > A[largest] to A[l] < A[smallest] (and likewise A[r] < A[smallest]). The crown step itself is unchanged — it still swaps the root to the back — but now the root is the minimum, so the smallest values get frozen at the far right and the array fills large-to-small from the front. Why exactly this change? The whole machine (build loop, crown, shrink) is agnostic about what "best" means; only the two comparison operators decide whether the champion is the max or the min. Flipping those two >→< (and renaming largest→smallest) converts the entire algorithm with no other edits.

Answer (b): switch the two > comparisons in sift_down to < (min-heap). Concretely, min-heap sorting [4,10,3,5,1] yields the descending array [10,5,4,3,1].

Recall gauntlet