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

This page is the "no surprises" drill for heap sort. We enumerate every kind of input the algorithm can meet, then work a real example for each. By the end you will have watched sift-down, build-heap, and full sorts run on tiny arrays, duplicate-heavy arrays, already-sorted arrays, reversed arrays, and even a one-element array — so nothing on an exam can catch you cold.

The scenario matrix

Cell	Case class	What could go wrong / what to prove	Example
A	Degenerate size: $n = 0$ or $n = 1$	Loops must not run; no crash	Ex 1
B	Tiny generic array (mixed order)	Full build + full sort trace	Ex 2
C	Already ascending-sorted	Build still does work; still $O (n lo g n)$	Ex 3
D	Reverse-sorted (descending)	Input is almost a max-heap already	Ex 4
E	All keys equal (duplicates)	No swaps; proves instability isn't triggered but also shows why stability fails	Ex 5
F	The Phase-2 shrinking-size trap	Passing wrong `n` corrupts the sorted tail	Ex 6
G	Build-heap $O (n)$ counting (limiting behaviour)	Count actual sift steps vs the $\sum h / 2^{h}$ bound	Ex 7
H	Real-world word problem	Top- $k$ / leaderboard framing	Ex 8
I	Exam twist: min-heap for descending order	Choosing heap type to match desired order	Ex 9

Every cell A–I is covered by exactly one example below.

Example 1 — Cell A: degenerate sizes

Worked example Sort

[] and [42]. Forecast: guess before reading — does the code crash on an empty array? What happens with one element?

Steps (empty array []):

n = len(A) = 0. Why this step? Every loop bound is derived from n.
Phase-1 loop range(n//2 - 1, -1, -1) = range(-1, -1, -1) = empty. Why? 0//2 - 1 = -1, and Python's range(-1,-1,-1) yields nothing, so no sift runs.
Phase-2 loop range(n-1, 0, -1) = range(-1, 0, -1) = empty. Why? No extraction is possible.
Result: [] unchanged. ✔

Steps (single element [42]):

n = 1. Phase-1 loop = range(-1,-1,-1) = empty (the lone element is a leaf = a valid heap by itself). Why? A single node trivially satisfies "parent $\geq$ children" — it has no children.
Phase-2 loop = range(0,0,-1) = empty. Why? With one element there is nothing to swap out.
Result: [42]. ✔

Verify: both arrays returned sorted (a length-0 or length-1 array is always sorted). No index ever exceeds bounds because both loops were empty.

Example 2 — Cell B: full trace on a tiny mixed array

Worked example Fully sort

[4, 10, 3, 5, 1] ascending. Forecast: the sorted answer is [1,3,4,5,10]. Try to predict what the max-heap looks like after Phase 1.

Phase 1 — build max-heap. $n = 5$ , start at $i = 5//2 - 1 = 1$ .

i=1 (val 10): children idx3=5, idx4=1. Largest is 10 itself → no swap. Why this step? A parent already $\geq$ both children needs nothing.
i=0 (val 4): children idx1=10, idx2=3. Largest=10 → swap idx0,idx1 → [10,4,3,5,1]. Follow down to idx1 (val 4): children idx3=5, idx4=1 → 5 largest → swap → [10,5,3,4,1]. idx3 is now a leaf → stop. Why follow down? One swap can violate the heap property one level lower, so sift-down chases the element all the way to its resting place.
Built heap: [10,5,3,4,1], root=10=max. ✔

Phase 2 — extract repeatedly. 4. Swap root↔idx4 → [1,5,3,4,|10]; heap size 4; sift idx0 (1): children 5,3 → swap 5 → [5,1,3,4,|10]; idx1 (1): children idx3=4 → swap → [5,4,3,1,|10]. Why? Park the max (10), fix the new small root. 5. Swap root↔idx3 → [1,4,3,|5,10]; size 3; sift idx0 (1): children idx1=4,idx2=3 → swap 4 → [4,1,3,|5,10]; idx1 leaf → stop. 6. Swap root↔idx2 → [3,1,|4,5,10]; size 2; sift idx0 (3): child idx1=1 → 3 largest → stop. 7. Swap root↔idx1 → [1,|3,4,5,10]; size 1 → loop ends. 8. Result: [1,3,4,5,10]. ✔

Verify: output equals sorted([4,10,3,5,1]) = [1,3,4,5,10]. Each parked element (10,5,4,3) was the max of the shrinking heap at that moment — a monotone decreasing sequence of maxima, exactly what sorted-descending-into-tail should be.

Example 3 — Cell C: already ascending-sorted input

Worked example Sort

[1, 2, 3, 4, 5] (already sorted). Forecast: does an already-sorted array skip work? (Trap: no — heap sort does not get faster on sorted input, unlike insertion sort.)

Phase 1 — build. $n = 5$ , start $i = 1$ .

i=1 (val 2): children idx3=4, idx4=5. Largest=5 → swap idx1,idx4 → [1,5,3,4,2]. Why? An ascending array is the worst possible max-heap layout — the smallest are on top.
i=0 (val 1): children idx1=5, idx2=3. Largest=5 → swap → [5,1,3,4,2]; down to idx1 (1): children idx3=4, idx4=2 → 4 largest → swap → [5,4,3,1,2]; idx3 leaf → stop.
Built heap: [5,4,3,1,2]. ✔ Notice: lots of swaps happened.

Phase 2 proceeds exactly like Ex 2's machinery and yields [1,2,3,4,5] (unchanged output, but real work done).

Verify: output = sorted([1,2,3,4,5]) = [1,2,3,4,5]. The lesson: same array in, same array out, but Phase 1 still performed swaps — heap sort's cost is $O (n lo g n)$ regardless of input order (no best-case speedup).

Example 4 — Cell D: reverse-sorted input

Worked example Sort

[5, 4, 3, 2, 1] (descending). Forecast: a descending array reads top-to-bottom as biggest-first — is it already a max-heap?

Phase 1 — build. $n = 5$ , start $i = 1$ .

i=1 (val 4): children idx3=2, idx4=1. 4 is largest → no swap. Why? Every parent already dominates.
i=0 (val 5): children idx1=4, idx2=3. 5 largest → no swap.
Built heap: [5,4,3,2,1] — unchanged. ✔ A descending array is a valid max-heap, so build does zero swaps.

Phase 2 — extract (this still does full work): 4. Swap idx0↔idx4 → [1,4,3,2,|5]; size 4; sift: 1<4 swap → [4,1,3,2,|5]; idx1(1) child idx3=2 → swap → [4,2,3,1,|5]. 5. Swap idx0↔idx3 → [1,2,3,|4,5]; size 3; sift: children 2,3 → swap 3 → [3,2,1,|4,5]; idx2 out of size → stop. 6. Swap idx0↔idx2 → [1,2,|3,4,5]; size 2; sift: child 2 → swap → [2,1,|3,4,5]. 7. Swap idx0↔idx1 → [1,|2,3,4,5]; size 1 → done. 8. Result: [1,2,3,4,5]. ✔

Verify: output = sorted([5,4,3,2,1]) = [1,2,3,4,5]. Build was free; Phase 2 was full — total still $O (n lo g n)$ .

Example 5 — Cell E: all keys equal + why heap sort is unstable

Worked example Sort

[7, 7, 7, 7] where the four 7's start as $7_{a}, 7_{b}, 7_{c}, 7_{d}$ (subscripts = original order). Forecast: if every key is equal, does the algorithm do any swaps? And does it keep $7_{a}$ before $7_{b}$ ?

Phase 1 — build. $n = 4$ , start $i = 1$ .

i=1 ( $7_{b}$ ): children idx3= $7_{d}$ . Condition A[l] > A[largest] is 7 > 7 → False (strict >). No swap. Why strict >? Using > (not \geq$) means equal children never trigger a swap — that's what keeps this array untouched.
i=0 ( $7_{a}$ ): children $7_{b}, 7_{c}$ , both 7 > 7 False → no swap.
Built heap: [7_a,7_b,7_c,7_d] unchanged. ✔

Phase 2 — extract: 4. Swap idx0↔idx3 → [7_d,7_b,7_c,|7_a]. Even though keys are equal, we still swap the physical slots. Now $7_{d}$ sits before $7_{b}$ — the original order is already scrambled. 5. Continuing extraction keeps swapping equal keys. Final array of keys: [7,7,7,7] (sorted by value) but the subscript order is not $a, b, c, d$ .

Verify: output keys = sorted([7,7,7,7]) = [7,7,7,7] ✔ (correct by value). But the subscripts got reordered by the very first extraction swap → this concretely demonstrates that heap sort is not stable. If you needed $7_{a}$ to stay before $7_{b}$ , use Merge Sort.

Example 6 — Cell F: the shrinking-size trap

Worked example From the mid-sort state

[5,4,3,1,|10] (heap size 4, 10 already sorted), run one extraction correctly, then show what a bug does. Forecast: what happens if you pass len(A)=5 to sift-down instead of the shrunk size?

Correct step (end=4):

Swap idx0↔idx3 → [1,4,3,5,|10] (5 now parked). Why? 5 is the max of the size-4 heap.
sift_down(A, 0, end=4) — but wait, end should now be 3 for the next round; for THIS restore we sift over size... Let's restate precisely: extraction at end=4 swaps A[0],A[4]? No — end indexes the last heap slot. Correct trace: swap A[0]↔A[3] (the last heap slot for size 4 is index 3) → [1,4,3,5,|10]; then sift_down(A, 0, 3) restores heap of size 3: children idx1=4,idx2=3 → swap 4 → [4,1,3,|5,10]. Why size 3? The slot that just received the max (index 3, value 5) must be frozen.

The bug (sift_down(A, 0, 5)): 3. With n=5, sift-down at idx0 sees children idx1,idx2 and could reach idx3=5 and idx4=10. It would drag the already-sorted 10 (or 5) back into the heap region → corruption. Why? The tail [5,10] is finished; letting sift-down peek at it destroys the sorted region.

Verify: correct path continues to sorted output; the buggy path re-imports 10 into position 0 on the next compare (A[4]=10 > A[0]), producing a non-sorted result. Rule: always pass the shrinking end, never len(A).

Example 7 — Cell G: build-heap $O (n)$ by literal step-counting

Worked example Count the actual sift-down

comparisons/moves during build-heap on a full tree of $n = 7$ : [1,2,3,4,5,6,7]. Forecast: the naive $n lo g n$ guess predicts $7 \times lo g_{2} 7 \approx 7 \times 2.8 \approx 20$ level-moves. The real count is much smaller — guess how much.

Phase 1 — build. $n = 7$ , internal nodes are $i = 2, 1, 0$ (since $7//2 - 1 = 2$ ).

i=2 (val 3, height 1 from bottom): children idx5=6, idx6=7. Swap with 7 → [1,2,7,4,5,6,3]. idx6 now leaf → stop. Moves: 1. Why height 1? Node 2 is one level above the leaves.
i=1 (val 2, height 1): children idx3=4, idx4=5. Swap with 5 → [1,5,7,4,2,6,3]. idx4 leaf → stop. Moves: 1.
i=0 (val 1, height 2 = root): children idx1=5, idx2=7. Swap with 7 → [7,5,1,4,2,6,3]; down to idx2 (1): children idx5=6,idx6=3 → swap 6 → [7,5,6,4,2,1,3]; idx5 leaf → stop. Moves: 2.
Total swap-moves = $1 + 1 + 2 = 4$ .

Compare to the bound. The formula says $T_{build} \leq n \sum_{h \geq 0} h / 2^{h} = 7 \times 2 = 14$ as an $O (n)$ ceiling; the naive $n lo g n$ guess was $\approx 20$ . Our exact swap count 4 sits comfortably below both, confirming build is linear-ish, not $n lo g n$ .

Verify: the two nodes at height 1 cost $\leq 1$ each and the one node at height 2 costs $\leq 2$ — matching $\sum_{h} (count at h) \cdot h = 2 \cdot 1 + 1 \cdot 2 = 4$ . Final built heap [7,5,6,4,2,1,3] is a valid max-heap (root 7 = max). ✔

Example 8 — Cell H: real-world word problem

Worked example A gaming leaderboard stores scores

[50, 20, 80, 10, 60, 40]. Publish the full ranking, highest first, in place with no extra memory. Forecast: which heap type, and what does the array look like after building?

Choose a max-heap so the top of the heap is the highest score. Why? We want the biggest score parked... but wait — heap sort with a max-heap parks the largest at the end, producing ascending order. To read highest-first, we sort ascending in place then read the array backwards (or reverse it). Why this trick? In-place with $O (1)$ space forbids a second array; reading the sorted array right-to-left costs nothing.
Build max-heap from [50,20,80,10,60,40]. $n = 6$ , start $i = 2$ .
- i=2 (80): children idx5=40 → 80 largest → no swap.
- i=1 (20): children idx3=10, idx4=60 → swap 60 → [50,60,80,10,20,40].
- i=0 (50): children idx1=60, idx2=80 → swap 80 → [80,60,50,10,20,40]; down idx2 (50): child idx5=40 → 50 largest → stop.
- Built: [80,60,50,10,20,40], root 80 = top score. ✔
Run Phase 2 → sorted ascending [10,20,40,50,60,80].
Read backwards → leaderboard [80,60,50,40,20,10].

Verify: sorted([50,20,80,10,60,40]) = [10,20,40,50,60,80]; reversed = [80,60,50,40,20,10]. Highest score 80 is first, lowest 10 last. In-place, $O (1)$ space, $O (n lo g n)$ time. ✔ (This is the same access pattern a Priority Queue gives for repeated max-extraction.)

Example 9 — Cell I: exam twist — min-heap to sort descending

Worked example "You have a

min-heap implementation only. Sort [3,1,2] into descending order in place." Do it without converting to a max-heap. Forecast: a min-heap puts the smallest at the root. If you park the smallest at the end each round, what order do you get?

A min-heap satisfies parent $\leq$ children, so root = minimum. Why relevant? Parking the min at the tail each round grows a descending sorted region from the right.
Build min-heap from [3,1,2]. $n = 3$ , start $i = 0$ (only internal node).
- i=0 (3): children idx1=1, idx2=2 → smallest child is 1 → swap → [1,3,2]; idx1 leaf → stop. Min-heap [1,3,2], root 1 = min. ✔
Extract-min into tail: swap idx0↔idx2 → [2,3,|1]; size 2; sift idx0 (2): child idx1=3 → 2 smaller → stop. Heap [2,3].
Swap idx0↔idx1 → [3,|2,1]; size 1 → done.
Result: [3,2,1]. ✔

Verify: sorted([3,1,2], reverse=True) = [3,2,1] matches. Rule to memorize: ==heap type is the opposite of the desired order's direction== — max-heap → ascending, min-heap → descending. (Because the extracted root is parked at the end, so the end fills with the extremes first.)

Recall checkpoint

Recall Does already-sorted input make heap sort faster?

No — Phase 1 still does swaps and Phase 2 always runs $n - 1$ extractions. Heap sort is $O (n lo g n)$ on every input (see Ex 3). Compare Quicksort which degrades on sorted input, and Introsort which switches to heap sort to avoid that.

Recall What size must you pass to sift-down in Phase 2?

The shrinking end, not len(A) — otherwise the sorted tail leaks back into the heap (Ex 6).

Recall Max-heap gives which sort order, min-heap gives which?

Max-heap → ascending; min-heap → descending (Ex 9). The extreme gets parked at the far end each round.

Which cell covers all-equal keys and instability?

Cell E — Example 5, [7,7,7,7].

Which cell proves build-heap is not

O (n lo g n)

by counting?

Cell G — Example 7 (4 swap-moves for

n = 7

For descending order with only a min-heap available, what do you park where?

Park the extracted minimum at the tail each round → tail fills descending.

Connections

Heap sort — in-place, O(n log n) — the parent this drill supports.
Binary Heap — the structure every example manipulates.
Priority Queue — Example 8's repeated max-access pattern.
Merge Sort — use it instead when stability matters (Example 5).
Quicksort — the sorted-input contrast in Example 3.
Introsort — falls back to heap sort to guarantee $O (n lo g n)$ worst case.