Heap sort — O(n log n), in-place, not stable: Exercises

Throughout, arrays are 0-indexed and we build a max-heap (every parent $\geq$ its children). Recall the three index formulas:

Level 1 — Recognition

L1.1 — Is it a heap?

Consider the array $A = [9, 7, 8, 3, 4, 5]$ . Draw it as a tree and decide: is it a valid max-heap?

Recall Solution

Place the values level by level, left to right. Index 0 is the root, indices 1–2 are the next level, indices 3–5 the last.

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

Figure s01: the six values drawn as a tree. Each node is labelled with its array index (yellow) so you can see how the flat array maps onto parent/child links. The green edges are the parent→child comparisons you must check; trace each edge and confirm the upper number is $\geq$ the lower one — the visual makes the "check vertically" rule concrete in a way the array of numbers alone does not.

Check every parent against its children:

Node 0 ( $9$ ): children are index 1 ( $7$ ) and index 2 ( $8$ ). $9 \geq 7$ and $9 \geq 8$ . ✅
Node 1 ( $7$ ): children are index 3 ( $3$ ) and index 4 ( $4$ ). $7 \geq 3$ and $7 \geq 4$ . ✅
Node 2 ( $8$ ): children are index 5 ( $5$ ) and index 6 (does not exist). $8 \geq 5$ . ✅

Every parent dominates its children, so yes, it is a valid max-heap.

L1.2 — Find the family

In $A = [50, 30, 40, 10, 20, 35, 25]$ , what is the parent, left child, and right child of the node at index $2$ (value $40$ )?

Recall Solution

Plug $i = 2$ into the formulas.

parent $= ⌊(2 - 1) /2 ⌋ = ⌊ 0.5 ⌋ = 0$ → value $50$ .
left child $= 2 (2) + 1 = 5$ → value $35$ .
right child $= 2 (2) + 2 = 6$ → value $25$ .

So $40$ 's parent is $50$ , and its children are $35$ and $25$ . (Sanity: $40 \geq 35$ and $40 \geq 25$ , so the heap property holds here.)

Level 2 — Application

L2.1 — One sift-down

Given the array $A = [4, 9, 8, 3, 5]$ (heap size $n = 5$ ), run sift_down(A, 0, 5) on the root. Show the array after it finishes.

Recall Solution

The root ( $4$ ) is too small; sift-down pushes it down until both its children are $\leq$ it.

Figure s02: the same tree with the sinking value $4$ and its downward path drawn in red. The two red arrows show the exact swaps sift-down performs — first $4 \leftrightarrow 9$ (idx 0↔1), then $4 \leftrightarrow 5$ (idx 1↔4). The blue nodes are untouched. This picture answers "how far does $4$ actually fall?" — you can literally count the two arrow hops rather than re-simulating the loop in your head.

Iteration 1: $i = 0$ , children $l = 1$ ( $9$ ), $r = 2$ ( $8$ ). Largest of ${4, 9, 8}$ is index 1. Swap indices 0 and 1: $[4, 9, 8, 3, 5] \to [9, 4, 8, 3, 5]$ Now follow the demoted $4$ : $i = 1$ .

Iteration 2: $i = 1$ , children $l = 3$ ( $3$ ), $r = 4$ ( $5$ ). Largest of ${4, 3, 5}$ is index 4. Swap indices 1 and 4: $[9, 4, 8, 3, 5] \to [9, 5, 8, 3, 4]$ Now $i = 4$ .

Iteration 3: $i = 4$ . Its left child would be $2 (4) + 1 = 9 \geq n$ , so it has no children. largest == i, loop breaks.

Final array: $[9, 5, 8, 3, 4]$ — a valid max-heap.

L2.2 — Build-max-heap by hand

Turn $A = [3, 1, 6, 5, 2, 4]$ ( $n = 6$ ) into a max-heap. The build loop starts at $i = ⌊ \frac{n}{2} ⌋ - 1 = ⌊ 3 ⌋ - 1 = 2$ and counts down to $0$ . Show the array after each sift_down.

Recall Solution

We only sift the internal (non-leaf) nodes, indices $2, 1, 0$ . Leaves (indices 3,4,5) are already trivially heaps.

$i = 2$ (value $6$ ): children $l = 5$ ( $4$ ), $r = 6$ (none). Largest of ${6, 4}$ is index 2 itself. No swap. $[3, 1, 6, 5, 2, 4]$

$i = 1$ (value $1$ ): children $l = 3$ ( $5$ ), $r = 4$ ( $2$ ). Largest of ${1, 5, 2}$ is index 3. Swap 1↔3: $[3, 5, 6, 1, 2, 4]$ Follow $1$ to $i = 3$ : child $l = 7 \geq 6$ , no children. Stop.

$i = 0$ (value $3$ ): children $l = 1$ ( $5$ ), $r = 2$ ( $6$ ). Largest of ${3, 5, 6}$ is index 2. Swap 0↔2: $[6, 5, 3, 1, 2, 4]$ Follow $3$ to $i = 2$ : children $l = 5$ ( $4$ ), $r = 6$ (none). Largest of ${3, 4}$ is index 5. Swap 2↔5: $[6, 5, 4, 1, 2, 3]$ Follow to $i = 5$ : leaf. Stop.

Final heap: $[6, 5, 4, 1, 2, 3]$ . Verify root $6$ is the maximum — good.

Level 3 — Analysis

L3.1 — Why $O (n)$ to build, not $O (n lo g n)$

The naive guess: build calls sift-down on $\sim n /2$ nodes, each costing $O (lo g n)$ , so build is $O (n lo g n)$ . But the true bound is $O (n)$ . Explain the gap.

Recall Solution

The naive bound is not wrong, just loose. It over-charges by assuming every node can fall the full height $lo g n$ . But most nodes are near the bottom and can barely fall at all.

Count by height $h$ (leaves have $h = 0$ ). A tree of $n$ nodes has at most $⌈ \frac{n}{2 ^{h + 1}} ⌉$ nodes at height $h$ , and each can fall at most $h$ levels. Total work: $T (n) \leq \sum_{h = 0}^{⌊ l o g_{2} n ⌋} \frac{n}{2 ^{h + 1}} \cdot h = \frac{n}{2} \sum_{h = 0}^{\infty} \frac{h}{2 ^{h}} .$ Why is $S = \sum_{h = 0}^{\infty} h / 2^{h}$ exactly $2$ ? Write it out and use a shift trick. Let $S = \frac{0}{1} + \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \dots$ Halve every term (this shifts the sequence one slot right): $\frac{1}{2} S = \frac{0}{2} + \frac{1}{4} + \frac{2}{8} + \frac{3}{16} + \dots$ Subtract the second line from the first. Each coefficient drops by exactly $1$ , leaving a plain geometric series: $S - \frac{1}{2} S = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots = 1.$ So $\frac{1}{2} S = 1$ , giving $S = 2$ . (The geometric series $\frac{1}{2} + \frac{1}{4} + \dots$ sums to $1$ because it is $\frac{1/2}{1 - 1/2}$ .) Therefore $T (n) \leq \frac{n}{2} \cdot 2 = n ⟹ T (n) = O (n) .$

Picture: the many cheap leaves (half the nodes, cost 0) dwarf the few expensive nodes near the root. The geometric decay of $1/ 2^{h}$ beats the linear growth of $h$ .

L3.2 — Best case is still $Θ (n lo g n)$

Merge sort and heap sort are both $O (n lo g n)$ . But quicksort has a bad $O (n^{2})$ case and insertion sort has a lovely $O (n)$ best case. What is heap sort's best case, and why can't it be faster?

Recall Solution

Even on an already-sorted or all-equal array, the sort-down phase must do its full work: $n - 1$ times it swaps the root to the back and calls sift-down on a heap of shrinking size $k$ . Each such sift-down on the root of a size- $k$ heap costs $Θ (lo g k)$ in the worst path, and — crucially — the value swapped up from the back is a small leaf value, so it almost always sinks the full height.

Summing the sort-down cost: $\sum_{k = 2}^{n} lo g_{2} k = lo g_{2} (n!) .$ Why is $lo g_{2} (n!) = Θ (n lo g n)$ ? Bound it from both sides.

Upper bound: every factor in $n! = 1 \cdot 2 \dots n$ is $\leq n$ , so $n! \leq n^{n}$ , hence $lo g_{2} (n!) \leq n lo g_{2} n$ . That gives the $O (n lo g n)$ side.
Lower bound: the top half of the factors, from $\frac{n}{2}$ up to $n$ (there are $\frac{n}{2}$ of them), are each $\geq \frac{n}{2}$ . So $n! \geq (\frac{n}{2})^{n /2}$ , hence $lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2} = \frac{n}{2} (lo g_{2} n - 1) = Ω (n lo g n)$ .

Squeezed between $Ω (n lo g n)$ and $O (n lo g n)$ , we get $lo g_{2} (n!) = Θ (n lo g n)$ . (This is the elementary version of Stirling's approximation $ln n! \approx n ln n - n$ .) There is no input that lets sift-down "get lucky and stop early" across all $n - 1$ rounds. Hence heap sort is $Θ (n lo g n)$ in best, average, and worst cases — remarkably consistent, unlike quicksort.

Level 4 — Synthesis

L4.1 — Full trace, first two crownings

Take the heap from L2.2, $A = [6, 5, 4, 1, 2, 3]$ . Run the sort-down phase: swap(A[0], A[end]); sift_down(A,0,end) for end = 5 then end = 4. Show the array after each of these two crownings. Which values are now locked in the sorted tail?

Recall Solution

end = 5. Swap root and index 5: $[6, 5, 4, 1, 2, 3] \to [3, 5, 4, 1, 2, 6]$ . The $6$ is now locked in place at the end. Heap shrinks to indices $0..4$ ; sift-down index 0 over $n = 5$ :

$i = 0$ : children $l = 1$ ( $5$ ), $r = 2$ ( $4$ ). Largest index 1. Swap 0↔1: $[5, 3, 4, 1, 2 ∣ 6]$ .
$i = 1$ : children $l = 3$ ( $1$ ), $r = 4$ ( $2$ ). Largest of ${3, 1, 2}$ is index 1 itself. Stop.
Array: $[5, 3, 4, 1, 2 ∣ 6]$ .

end = 4. Swap index 0 and index 4: $[5, 3, 4, 1, 2 ∣6] \to [2, 3, 4, 1, 5 ∣ 6]$ . The $5$ is locked. Heap shrinks to indices $0..3$ ; sift-down index 0 over $n = 4$ :

$i = 0$ : children $l = 1$ ( $3$ ), $r = 2$ ( $4$ ). Largest index 2. Swap 0↔2: $[4, 3, 2, 1 ∣ 5, 6]$ .
$i = 2$ : child $l = 5 \geq 4$ , no children. Stop.
Array: $[4, 3, 2, 1 ∣ 5, 6]$ .

After two crownings the array is $[4, 3, 2, 1, 5, 6]$ and the sorted tail holds ${5, 6}$ .

L4.2 — Complete the sort

Continue L4.1 from $[4, 3, 2, 1 ∣ 5, 6]$ (active heap = first 4 slots) to the fully sorted array. Show every crowning.

Recall Solution

end = 3. Swap 0↔3: $[1, 3, 2 ∣ 4, 5, 6]$ . Sift-down 0 over $n = 3$ :

$i = 0$ : children $l = 1$ ( $3$ ), $r = 2$ ( $2$ ). Largest index 1. Swap: $[3, 1, 2 ∣ 4, 5, 6]$ .
$i = 1$ : child $l = 3 \geq 3$ , no children. Stop → $[3, 1, 2 ∣ 4, 5, 6]$ .

end = 2. Swap 0↔2: $[2, 1 ∣ 3, 4, 5, 6]$ . Sift-down 0 over $n = 2$ :

$i = 0$ : child $l = 1$ ( $1$ ). Largest is index 0. Stop → $[2, 1 ∣ 3, 4, 5, 6]$ .

end = 1. Swap 0↔1: $[1, 2, 3, 4, 5, 6]$ . Sift-down 0 over $n = 1$ : no children. Loop end ends at 1.

Final: $[1, 2, 3, 4, 5, 6]$ — fully sorted. ✅

Level 5 — Mastery

L5.1 — Stability counterexample (find the minimum size)

Heap sort is not stable. Find the smallest array of records with a key and a tag that proves it — i.e. two equal keys end up in swapped original order after sorting. Justify why your size is minimal.

Recall Solution

"Stable" means equal keys keep their original left-to-right order. We need two equal keys that heap sort reorders. Write records as $key_{tag}$ , sorting ascending by key.

The minimum is $n = 2$ . (You cannot do it with $n \leq 1$ : with $0$ or $1$ record there is no pair of equal keys to reorder at all.) Take $A = [1_{a}, 1_{b}]$ (two equal keys, $a$ before $b$ ):

Build: the only internal node is index $⌊ 2/2 ⌋ - 1 = 0$ . sift-down(0) over $n = 2$ : child index 1 has key $1$ , which is not strictly greater than the root's key $1$ , so no swap. Heap stays $[1_{a}, 1_{b}]$ .
Sort-down end=1: swap root and index 1: $[1_{b}, 1_{a}]$ , then lock index 1. sift-down(0) over the shrunk $n = 1$ : no children, nothing happens.
Final: $[1_{b}, 1_{a}]$ .

The single final swap flips the equal keys from $a, b$ to $b, a$ — original order broken. So the smallest witness is just two equal elements, and that lone crowning swap is the whole reason heap sort is unstable.

(Aside: a $3$ -element array like $[1_{a}, 1_{b}, 2]$ also fails, but it is not minimal — the $2$ is irrelevant to the instability, which lives entirely in the equal-key swap.)

L5.2 — Degenerate inputs

State precisely what heap sort does on: (a) an empty array $[]$ , (b) a single element $[7]$ , (c) all-equal $[5, 5, 5, 5]$ . No swaps happen in some — say which and why.

Recall Solution

(a) $[]$ , $n = 0$ . Build loop starts at $i = ⌊ 0/2 ⌋ - 1 = - 1$ and counts down to 0 — it never runs (start already below 0). Sort-down loop runs end from $n - 1 = - 1$ down to 1 — never runs. Zero operations, output $[]$ . Correctly sorted (vacuously).

(b) $[7]$ , $n = 1$ . Build starts at $i = ⌊ 1/2 ⌋ - 1 = - 1$ down to 0 → doesn't run. Sort-down runs end from $0$ down to $1$ → doesn't run. Zero swaps, output $[7]$ .

(c) $[5, 5, 5, 5]$ , $n = 4$ . Build sifts $i = 1, 0$ . Every comparison uses strict >; since all values are equal, no child is ever strictly greater, so largest never moves — no swaps in build. Sort-down still runs $n - 1 = 3$ times, each swapping root with the back (swapping equal values — harmless) then sifting with no strict-greater child, so no further movement. Output $[5, 5, 5, 5]$ , sorted. Note: the swaps here are "wasted work" but the strict > guard keeps sift-down from looping forever.

Recall Self-check (how to use these)

The lines below are active recall prompts. For each ==highlighted== term, cover the sentence and try to say the highlighted word before revealing it. For each Question ::: Answer line, read only the part before :::, answer aloud, then check yourself against the part after :::. In Obsidian these render as click-to-reveal.

A heap sort's build phase costs == $O (n)$ while the sort-down phase costs $O (n lo g n)$ . sift-down assumes the node's subtrees are already valid heaps. Heap sort is not stable because the build/crown swaps move equal keys across each other==. Best case for heap sort ::: $Θ (n lo g n)$ — no input lets it finish faster. Why start build at index $⌊ n /2 ⌋ - 1$ ::: it is the last internal (non-leaf) node; everything after is a leaf and already a heap.