Heapify — bottom-up O(n) build: Worked examples

This page is the "throw everything at it" companion to the parent Heapify note. There we derived why bottom-up build is $O (n)$ . Here we drill the algorithm by hand across every kind of input it could ever meet — tiny arrays, already-sorted arrays, all-equal arrays, the empty degenerate case, a real-world word problem, and an exam trap.

Before we start, one reminder in plain words. A ==heap== is an array we pretend is a filling-left-to-right binary tree (a Complete Binary Tree). For a max-heap every parent is $\geq$ its two children; for a min-heap every parent is $\leq$ its children. siftDown(i) takes the value at slot i and lets it sink by repeatedly swapping with its larger (max-heap) child until it is bigger than both children or hits the bottom. Bottom-up build calls siftDown on every non-leaf, from index $⌊ n /2 ⌋ - 1$ up to $0$ . Every symbol you meet below was defined here or in the parent — if you forget one, glance back.

Three short-hand names appear in every step below, so let us pin them down here on this page so you never have to hunt:

The index map we lean on constantly:

The scenario matrix

Heapify has fewer "quadrants" than trigonometry, but it still has genuinely distinct shapes of input. If a worked-examples page skips even one of these, you will one day hit a case you were never shown. Here is the full grid.

Cell	What makes it distinct	Covered by
A. Generic max-heap	Random values, several real swaps, a cascading sink	Ex 1
B. Generic min-heap	Same algorithm, flipped comparison	Ex 2
C. Already a valid heap	Every `siftDown` breaks immediately — best case	Ex 3
D. Reverse-sorted input	Worst shape: root value is smallest, must sink fully	Ex 4
E. All-equal elements	Ties everywhere — must confirm no infinite loop / no wasted swaps	Ex 5
F. Even $n$ with a lone left child	The "right child out of bounds" guard actually fires	Ex 6
G. Degenerate sizes	$n = 0$ and $n = 1$ : the loop never runs — why that's correct	Ex 7
H. Real-world word problem	Priority-scheduling story mapped onto a heap	Ex 8
I. Exam twist	"How many swaps total?" — probes the $O (n)$ intuition, not just the answer	Ex 9

We now walk one example per cell (Ex 1 doubles as the cascade demo with a figure).

Cell A — generic max-heap, with a cascade

Worked example Ex 1 (Cell A) — max-heap from

[3, 9, 2, 1, 4, 5] $n = 6$ , last internal node $= ⌊ 6/2 ⌋ - 1 = 2$ . Process $i = 2, 1, 0$ .

Forecast: guess the final array before reading on. (Hint: the biggest value, $9$ , must end at index $0$ .)

Starting tree by index: 0=3, 1=9, 2=2, 3=1, 4=4, 5=5.

Step 1 — siftDown(2). Node 2 (value $2$ ) has only a left child at $l = 2 \cdot 2 + 1 = 5$ (value $5$ ). Since $5 > 2$ , largest becomes $5$ → swap. Array → [3,9,5,1,4,2]. Why this step? We start at the last internal node because everything after it is a leaf and already trivially a valid heap — no point sifting leaves.

Step 2 — siftDown(1). Node 1 (value $9$ ) has children at $l = 3$ ( $= 1$ ) and $r = 4$ ( $= 4$ ). Both are smaller than $9$ , so largest stays $i$ and we break — no swap. Array unchanged: [3,9,5,1,4,2]. Why this step? The whole subtree under index 1 is now a valid max-heap, ready for its parent (the root) to rely on.

Step 3 — siftDown(0), first swap. Node 0 (value $3$ ) has children at $l = 1$ ( $= 9$ ) and $r = 2$ ( $= 5$ ). largest becomes $1$ (value $9$ ). Swap. Array → [9,3,5,1,4,2]. Why this step? The root must hold the maximum of its two child-subtrees, and $9 > 5$ , so the winner is the left child.

Step 4 — the cascade. The demoted $3$ now sits at index $1$ . Follow it: children at $l = 3$ ( $= 1$ ) and $r = 4$ ( $= 4$ ). largest becomes $4$ → swap. Array → [9,4,5,1,3,2]. The $3$ now lands at index $4$ , which is a leaf → stop. Why this step? A single swap at the root does not finish the job — the demoted value can still violate the property lower down, so siftDown keeps following it. This is the "cascade" the figure below highlights.

The figure. The picture shows the final tree [9,4,5,1,3,2]. The two coral arrows trace the exact path the demoted value $3$ took: first the root swap ( $3 \leftrightarrow 9$ , coral node at index 0 → index 1), then the second swap ( $3 \leftrightarrow 4$ , index 1 → index 4). The coral nodes are the slots $3$ passed through; the mint node (index 2, value 5) and lavender leaves (indices 3, 5) were never touched. Reading the coral trail top-to-bottom is the cascade.

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

Verify: parent-child checks — $9 \geq 4, 5$ ✓; $4 \geq 1, 3$ ✓; $5 \geq 2$ ✓. Every parent dominates its children ⇒ valid max-heap.

Cell B — generic min-heap (same algorithm, flipped test)

Worked example Ex 2 (Cell B) — min-heap from

[5, 1, 8, 2, 7] $n = 5$ , last internal $= ⌊ 5/2 ⌋ - 1 = 1$ . Process $i = 1, 0$ . Min-heap ⇒ parent $\leq$ children, so siftDown chases the smallest child (the bookmark is smallest instead of largest).

Forecast: the smallest value $1$ must end at index $0$ . Where does $5$ end up?

Step 1 — siftDown(1). Node 1 (value $1$ ) has children at $l = 3$ ( $= 2$ ) and $r = 4$ ( $= 7$ ). $1$ is already smallest → smallest stays $i$ → no swap. Why this step? Nothing to fix here; the subtree is a valid min-heap and can be trusted by the root.

Step 2 — siftDown(0). Node 0 (value $5$ ) has children at $l = 1$ ( $= 1$ ) and $r = 2$ ( $= 8$ ). smallest becomes $1$ → swap indices $0, 1$ . Array → [1,5,8,2,7]. Why this step? The root of a min-heap must hold the global-so-far minimum among its children.

Step 3 — cascade the $5$ . The $5$ now sits at index $1$ ; children at $l = 3$ ( $= 2$ ) and $r = 4$ ( $= 7$ ). smallest becomes $2$ → swap. Array → [1,2,8,5,7]. The $5$ lands at index $3$ , a leaf → stop. Why this step? Same reason as Ex 1's cascade — one swap does not guarantee the sunk value is settled.

Result: [1,2,8,5,7].

Verify: $1 \leq 2, 8$ ✓; $2 \leq 5, 7$ ✓. Valid min-heap.

Cell C — input that is already a valid heap (best case)

Worked example Ex 3 (Cell C) — max-heap from

[9, 7, 8, 3, 6, 5] $n = 6$ , last internal $= 2$ . Process $i = 2, 1, 0$ .

Forecast: if this is already a heap, how many swaps happen? Guess before the steps.

Step 1 — siftDown(2). Value $8$ , only child at $l = 5$ ( $= 5$ ). $8 > 5$ , so largest stays $i$ → break, no swap. Why this step? Node 2 already dominates its lone child, so the first comparison already reports largest == i and exits — the built-in early exit costs one comparison, zero swaps.

Step 2 — siftDown(1). Value $7$ , children $l = 3$ ( $= 3$ ), $r = 4$ ( $= 6$ ). Both smaller → largest stays $i$ → break, no swap. Why this step? $7$ is already bigger than both children, so again the loop exits after one round — no work propagates downward.

Step 3 — siftDown(0). Value $9$ , children $l = 1$ ( $= 7$ ), $r = 2$ ( $= 8$ ). Both smaller → largest stays $i$ → break, no swap. Why this step? The root already holds the global maximum, so the early exit fires one last time; the whole array was never disturbed.

Result: [9,7,8,3,6,5] (unchanged). Total swaps $= 0$ .

Verify: $9 \geq 7, 8$ ; $7 \geq 3, 6$ ; $8 \geq 5$ ✓. Already a heap, confirmed. This shows the best case: linear number of comparisons, zero swaps.

Cell D — reverse-sorted, the worst shape

Worked example Ex 4 (Cell D) — max-heap from

[1, 2, 3, 4, 5, 6, 7] $n = 7$ , last internal $= ⌊ 7/2 ⌋ - 1 = 2$ . Process $i = 2, 1, 0$ . Ascending order is the worst input for a max-heap: the small values start on top and every one must sink.

Forecast: the max $7$ ends at index $0$ , but by what route? Guess how far the value $1$ (at the root) travels.

Indices: 0=1,1=2,2=3,3=4,4=5,5=6,6=7.

Step 1 — siftDown(2). Value $3$ , children $l = 5$ ( $= 6$ ), $r = 6$ ( $= 7$ ). largest becomes $6$ (value $7$ ) → swap $2 \leftrightarrow 6$ . Array → [1,2,7,4,5,6,3]. Index $6$ is a leaf → stop. Why this step? Node 2 must adopt the larger of its two children, and $7 > 6$ .

Step 2 — siftDown(1). Value $2$ , children $l = 3$ ( $= 4$ ), $r = 4$ ( $= 5$ ). largest becomes $4$ (value $5$ ) → swap $1 \leftrightarrow 4$ . Array → [1,5,7,4,2,6,3]. Index $4$ is a leaf → stop. Why this step? Same rule one level up; $5 > 4$ .

Step 3 — siftDown(0), the long fall. Value $1$ , children $l = 1$ ( $= 5$ ), $r = 2$ ( $= 7$ ). largest becomes $2$ (value $7$ ) → swap $0 \leftrightarrow 2$ . Array → [7,5,1,4,2,6,3]. The $1$ is now at index $2$ ; its children are $l = 5$ ( $= 6$ ), $r = 6$ ( $= 3$ ). largest becomes $5$ (value $6$ ) → swap $2 \leftrightarrow 5$ . Array → [7,5,6,4,2,1,3]. The $1$ is now at index $5$ , a leaf → stop. Why this step? The root value $1$ was the global minimum, so it cascades all the way to a leaf — this is the maximal-work path a single siftDown can take (height of the root $= ⌊ lo g_{2} 7 ⌋ = 2$ levels).

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

Verify: $7 \geq 5, 6$ ; $5 \geq 4, 2$ ; $6 \geq 1, 3$ ✓. Valid max-heap. Notice even in the worst shape only the root did a full 2-level fall — the numerous lower nodes fell $\leq 1$ level. That imbalance is exactly the $O (n)$ argument from the parent note in action.

Cell E — all elements equal (tie handling)

Worked example Ex 5 (Cell E) — max-heap from

[4, 4, 4, 4, 4] $n = 5$ , last internal $= 1$ . Process $i = 1, 0$ .

Forecast: with every comparison a tie, how many swaps happen? Could the code loop forever?

Step 1 — siftDown(1). Children $l = 3$ ( $= 4$ ), $r = 4$ ( $= 4$ ). The test is A[l] > A[largest], a strict >. Since $4 > 4$ is false, largest stays $i$ → break, no swap. Step 2 — siftDown(0). Children $l = 1$ ( $= 4$ ), $r = 2$ ( $= 4$ ). Again $4 > 4$ is false → largest stays $i$ → break, no swap. Why these steps? The strict inequality means equal children never overtake largest, so it never leaves $i$ and no swap fires. Equal values already satisfy parent $\geq$ child (equality is allowed), so nothing needs to move.

Result: [4,4,4,4,4] (unchanged), $0$ swaps.

Verify: $4 \geq 4$ everywhere ✓ — valid. Crucially, the strict > guarantees no infinite loop: with >= you could swap two equal values forever. This is why the parent's pseudocode uses >, not >=.

Cell F — even $n$ , a node with only a left child

Worked example Ex 6 (Cell F) — max-heap from

[2, 10, 3, 4] $n = 4$ (an even size). Last internal $= ⌊ 4/2 ⌋ - 1 = 1$ . Process $i = 1, 0$ . When $n$ is even the very last leaf is a left child with no right sibling, so its parent has only one child and the right-child index runs past the array end. Here node $1$ 's right child would be $r = 2 \cdot 1 + 2 = 4$ , which is out of bounds ( $4 \neq < n = 4$ ) — the bounds guard r < n must fire.

Forecast: the guard r < n decides whether index $4$ is even looked at. What happens at node 1?

Indices: 0=2, 1=10, 2=3, 3=4.

Step 1 — siftDown(1). Left child $l = 3$ ( $= 4$ ): is $4 > 10$ ? No, so largest stays $i$ . Right child $r = 4$ : the guard r < n is $4 < 4$ , which is false, so we skip the right child entirely — no out-of-bounds read. largest == i → break, no swap. Why this step? The r < n guard is precisely what prevents indexing past the array when a node (as here, with even $n$ ) has only a left child.

Step 2 — siftDown(0). Children $l = 1$ ( $= 10$ ), $r = 2$ ( $= 3$ ). largest becomes $1$ (value $10$ ) → swap $0 \leftrightarrow 1$ . Array → [10,2,3,4]. The $2$ is now at index $1$ ; its left child $l = 3$ ( $= 4$ ): $4 > 2$ → largest becomes $3$ → swap $1 \leftrightarrow 3$ . Array → [10,4,3,2]. Its right child $r = 4$ again fails the guard $4 < 4$ , so it is skipped. Index $3$ is a leaf → stop. Why this step? After the root swap, the demoted $2$ still has a valid left child ( $4$ ) larger than it, so it keeps sinking; the right-child guard is evaluated at index 1 both before and after the swap and correctly skips the missing right child each time.

Result: [10,4,3,2].

Verify: $10 \geq 4, 3$ ; $4 \geq 2$ ✓ — valid max-heap, and no array-out-of-bounds ever occurred.

Cell G — degenerate sizes $n = 0$ and $n = 1$

Cell H — a real-world word problem

Worked example Ex 8 (Cell H) — building a task

Priority Queue A print server receives 6 jobs whose priority scores (higher = more urgent) arrive as the array [15, 3, 40, 20, 25, 10]. Build a max-heap so the most urgent job is at the front, ready for a Priority Queue / Heapsort.

Forecast: which score sits at index $0$ after heapify? (The most urgent one — but which value, and did $25$ have to move?)

$n = 6$ , last internal $= 2$ . Indices: 0=15,1=3,2=40,3=20,4=25,5=10.

Step 1 — siftDown(2). Value $40$ , only child $l = 5$ ( $= 10$ ). Is $10 > 40$ ? No → largest stays $i$ → break, no swap. Why? The already-urgent $40$ dominates its child; nothing to do.

Step 2 — siftDown(1). Value $3$ , children $l = 3$ ( $= 20$ ), $r = 4$ ( $= 25$ ). largest becomes $4$ (value $25$ ) → swap $1 \leftrightarrow 4$ . Array → [15,25,40,20,3,10]. The $3$ at index $4$ is a leaf → stop. Why? The low-priority job (score $3$ ) sinks so a more urgent job ( $25$ ) rises toward the front.

Step 3 — siftDown(0). Value $15$ , children $l = 1$ ( $= 25$ ), $r = 2$ ( $= 40$ ). largest becomes $2$ (value $40$ ) → swap $0 \leftrightarrow 2$ . Array → [40,25,15,20,3,10]. The $15$ is now at index $2$ ; only child $l = 5$ ( $= 10$ ): $10 > 15$ ? No → stop. Why? The globally most-urgent job ( $40$ ) claims index $0$ ; the demoted $15$ still beats its remaining child, so it settles quickly.

Result: [40,25,15,20,3,10] — job with score $40$ is served first.

Verify: $40 \geq 25, 15$ ; $25 \geq 20, 3$ ; $15 \geq 10$ ✓. The front of the queue holds the maximum priority, exactly what a scheduler needs.

Cell I — the exam twist

Worked example Ex 9 (Cell I) — "how many swaps total to heapify

[1,2,3,4,5,6,7]?" This is the exam favourite: it looks like it wants a number, but it is really testing whether you believe the $O (n)$ bound (see also Amortized Analysis and the Geometric Series sum from the parent).

Forecast: the loose bound would suggest up to $n ⌊ lo g_{2} n ⌋ = 7 \cdot 2 = 14$ swaps. Guess the actual count.

We already heapified this exact array in Ex 4. Count its swaps:

Step 1 — siftDown(2): $1$ swap (2↔6). Why this contributes? This node sits at height $1$ ; it can sink at most one level, so it costs at most one swap — and it used it.

Step 2 — siftDown(1): $1$ swap (1↔4). Why this contributes? Also a height- $1$ internal node; same one-swap ceiling, again used once.

Step 3 — siftDown(0): $2$ swaps (0↔2, then 2↔5). Why this contributes? The root sits at height $2$ , so it alone can afford a two-level fall — and being the smallest value, it takes the full ride.

Result: $1 + 1 + 2 = 4$ swaps total.

Verify: $1 + 1 + 2 = 4$ . This concretely shows the parent's punchline: the crowded low nodes are cheap ( $1$ swap each), the rare tall node is the only "expensive" one ( $2$ swaps), and the sum stays small ( $4 ≪ 14$ ) — the mechanism behind $O (n)$ , not the loose $O (n lo g n)$ . Compare with siftUp vs siftDown: an insertion build of the same array forces the many leaves upward and racks up more swaps.

Recall Which cell was hardest for you?

Best case (already a heap) ::: Ex 3 — every siftDown early-exits, 0 swaps. Worst shape (ascending input) ::: Ex 4 — the root value cascades a full height. Ties / infinite-loop guard ::: Ex 5 — strict > means equal children never swap. Out-of-bounds right child ::: Ex 6 — even $n$ , the r < n guard fires and is skipped safely. $n = 0$ and $n = 1$ ::: Ex 7 — start index $⌊ n /2 ⌋ - 1 = - 1$ , loop never runs.

Related: Binary Heap · Complete Binary Tree · Heapsort · Priority Queue · siftUp vs siftDown · Amortized Analysis · Geometric Series