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

This is a worked-examples companion to the parent Heap Operations note. There we built the rules; here we run those rules through every kind of situation they can meet, so no exam question surprises you.

If a word here is new — "sift-up", "sift-down", "complete", "parent index" — go re-read the parent note first; this page assumes you have those in hand and only drills them.

Formula sift-down pseudocode — where the boundary guards live

The out-of-range checks $ℓ < n$ and $r < n$ are the whole reason we never crash. Their exact placement is: check the guard before you dereference the child.

sift-down(A, i, n):          # max-heap version
    loop:
        l = 2*i + 1          # left child index  (our ℓ)
        r = 2*i + 2          # right child index (our r)
        big = i
        if l < n and A[l] > A[big]:   big = l   # guard l < n FIRST
        if r < n and A[r] > A[big]:   big = r   # guard r < n FIRST
        if big == i: return             # node already dominates -> stop
        swap A[i], A[big]
        i = big

For a min-heap replace both > with < and rename big to small. Read the guards as: "only look at a child if its index is a real position ( $< n$ )."

The scenario matrix

Every heap problem is really one of the primitives (sift-up or sift-down) applied in a specific situation. The situations differ along a few axes. Below is every axis, and every value it can take. The examples afterward each fill in one row.

#	Case class	The tricky thing to watch	Example that hits it
A	insert, new key sinks to bottom	key is small → zero swaps, stays at leaf	Ex 1
B	insert, new key climbs to root	key is biggest → full-height climb	Ex 2
C	extract-max (max-heap), misfit sinks fully	root replacement is smallest → full path down	Ex 3
D	extract-max (max-heap), degenerate size	heap has 1 or 2 elements → boundary of index math	Ex 4
E	sift-down reaching a ONE-child parent	during a real extract, the sinking node meets a parent with a left child but no right → don't read out of range	Ex 5
F	decrease-key (min-heap) → sift-up	smaller value must go up	Ex 6
G	decrease-key (min-heap), no-op	new value still ≥ parent → zero swaps	Ex 7
H	increase-key (max-heap) → sift-up	larger value goes up in a max-heap	Ex 8
H′	increase-key (max-heap), no-op	new value still ≤ parent → zero swaps	Ex 8b
K	increase-key (min-heap) → sift-down	bigger value belongs lower in a min-heap	Ex 11
L	decrease-key (max-heap) → sift-down	smaller value belongs lower in a max-heap	Ex 12
I	word problem — real priority queue	mapping a story onto operations	Ex 9
J	exam twist — build-heap ordering	is a given array a valid heap? spot the violation	Ex 10

Reveal-yourself checks:

Which primitive does insert always use?

sift-up (append at the end, climb).

Which primitive does extract always use?

sift-down (move last to root, sink).

The two "zero swaps" cases are

an inserted key already ≤ its parent (max-heap), and a decrease-key whose new value is still ≥ its parent.

decrease-key on a max-heap uses

sift-down (a smaller value sinks toward the leaves).

increase-key on a min-heap uses

sift-down (a larger value sinks toward the leaves).

Ex 1 — Case A: insert a small key (it barely moves)

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

Figure 1 — Alt text: a max-heap tree of 6 nodes after inserting 3. Root 40 (ink) has children 30 (teal, index 1) and 20 (plum, index 2); 30 has children 10 and 5; 20 has one new child 3 (orange, index 5) drawn at the bottom. A short orange arrow beside node 3 is crossed out and labelled "3 < parent 20, no climb". Each node is tagged with its array index.

Ex 2 — Case B: insert the biggest key (full climb to root)

Figure 2 — Alt text: a max-heap tree of 6 nodes showing the climb of inserted value 99. The value 99 is drawn as an orange node with two upward orange arrows tracing its path: first from index 5 up to index 2, then from index 2 up to index 0 (the root). Old occupants 20 and 40 are shown shifting down. Labels read "swap 1: 99 > 20" and "swap 2: 99 > 40". Each node is tagged with its array index.

Ex 3 — Case C: extract-max where the misfit sinks all the way

Figure 3 — Alt text: a max-heap tree of 5 nodes after the last element 20 (drawn as the orange root node) has replaced the removed maximum. Root 20 sits above children 30 (teal, left) and 40 (plum, right); 30 has children 10 and 5. An orange arrow points from the root down toward the larger child 40, labelled "sinks to larger child". Each node is tagged with its array index.

Worked example extract-max from

[99, 30, 40, 10, 5, 20] Forecast: after removing 99, which element goes to the root, and how deep does it sink?

Steps.

Save $max = A [0] = 99$ .
Move last element (20) to root, shrink: [20,30,40,10,5], $n = 5$ . Why? Moving the last leaf to the root keeps the tree complete in $O (1)$ . Promoting a child instead would tear a hole (see the parent note's steel-manned mistake).
sift-down(0): children $A [ℓ] = A [1] = 30$ , $A [r] = A [2] = 40$ . Largest of ${20, 30, 40}$ is $40$ at index 2. $40 > 20$ → swap → [40,30,20,10,5], $i = 2$ . Why? The root must dominate; the larger child is promoted so both new siblings still obey the rule.
Now $i = 2$ : children would be $ℓ = 5, r = 6$ , but both $\geq n = 5$ → out of range, no children → stop.

Verify: return 99, heap [40,30,20,10,5]: $40 \geq 30, 20$ ; $30 \geq 10, 5$ . ✓ In Figure 3, the orange root node (20) travelled down one branch only (the orange arrow toward 40); that single root-to-leaf path is why extract is $O (lo g n)$ .

Ex 4 — Case D: degenerate sizes (heap of 2, then 1)

Worked example extract-max twice from the

two-element heap [8, 5] Forecast: with so few nodes, does the index math still behave? Watch the boundaries.

Steps — first extract.

Save max $= 8$ . Move last (5) to root, shrink: [5], $n = 1$ .
sift-down(0): left child index $ℓ = 2 \cdot 0 + 1 = 1$ , but $ℓ \geq n = 1$ → the guard $ℓ < n$ fails → out of range, no children. Why this matters? This is the exact boundary where a careless A[ℓ] read crashes. The guard $ℓ < n$ saves you.
Stop. Return 8, heap [5].

Steps — second extract.

Save max $= 5$ . Move last (itself) to root, shrink: [], $n = 0$ .
sift-down(0) on an empty heap: index 0 is already out of range → do nothing.
Return 5, heap empty.

Verify: extracted values in order: 8 then 5 — a descending sequence, exactly what repeated extract-max should give (this is the heart of Heapsort). ✓

Ex 5 — Case E: extract-max whose sinking node meets a ONE-child parent

Figure 4 — Alt text: a 6-node max-heap tree for [40,10,30,5,8,20]. Root 40 (ink) has children 10 (teal, index 1) and 30 (ink, index 2); node 10 has children 5 (index 3) and 8 (index 4); node 30 has a single real child 20 (plum, index 5) drawn with a solid edge, and a dashed edge to an empty dashed circle marked "—" at index 6, labelled "right child idx 6 >= n (guard r < n fails)". A teal label reads "misfit sinks here and meets a lone left child".

Worked example extract-max from

[40, 10, 30, 5, 8, 20] (6 elements) Forecast: after we drop the last element into the root and let it sink, it will land on a parent that has a left child but no right child. Will your comparison read out of range? Trace it.

Steps.

Save max $= A [0] = 40$ . Move last element (20) to root, shrink: [20,10,30,5,8], $n = 5$ . Why? Standard extract — last leaf to root keeps completeness in $O (1)$ .
sift-down(0): $ℓ = 1, r = 2$ ; $A [ℓ] = 10$ , $A [r] = 30$ . Largest of ${20, 10, 30}$ is $30$ at index 2 → swap → [30,10,20,5,8], $i = 2$ . Why? Root must dominate; promote the larger child.
Now the misfit (20) is at $i = 2$ . Compute $ℓ = 2 \cdot 2 + 1 = 5$ , $r = 2 \cdot 2 + 2 = 6$ . Guard: $ℓ = 5 < n = 5$ ? No ( $5 \geq 5$ ). And $r = 6 < 5$ ? No. Why this step? This is the lone-/no-child boundary the forecast promised — here index 2's would-be left child sits exactly at $n$ , so it has no children at all and we must not read A[5]. The guards catch it.
big stays $i$ → stop.

To see a parent with a genuine lone left child (left exists, right does not), watch node index 2 in the pre-shrink tree: its left child is index 5 (value 20), its right child would be index 6 — but $6 \geq n = 6$ , so the guard $r < n$ fails and only the left child is ever compared. This is the exact situation Figure 4 draws.

Verify: return 40, heap [30,10,20,5,8]: $30 \geq 10, 20$ ; $10 \geq 5, 8$ . ✓ In Figure 4 the plum node 20 is the lone left child of node 30; its missing right sibling is drawn as a dashed empty slot at index 6 — a reminder that the guard $r < n$ must run before any A[r] read.

Ex 6 — Case F: decrease-key on a min-heap (a small value climbs)

Figure 5 — Alt text: a min-heap tree of 5 nodes showing value 1 climbing after decrease-key. Node at index 3 turns orange (was 12, now 1) and two upward orange arrows trace its path: from index 3 to index 1, then index 1 to index 0 (root). Labels read "1 < 8" and "1 < 2". Displaced values 8 and 2 shift down. Each node tagged with its array index.

Ex 7 — Case G: decrease-key that does NOTHING (zero work)

Ex 8 — Case H: increase-key on a max-heap (the mirror of Ex 6)

Ex 8b — Case H′: increase-key on a max-heap that does NOTHING (zero work)

Ex 11 — Case K: increase-key on a MIN-heap (it sinks — sift-down)

Worked example Min-heap

[1, 2, 5, 8, 9], increase index 0 (value 1) to 7 Forecast: raising the root of a min-heap — does it climb or sink? Which primitive?

Steps.

Set $A [0] = 7$ : [7,2,5,8,9]. ( $7 \geq 1$ , an increase.) Why? A larger value no longer belongs at the top of a min-heap — the small end is the root, so 7 is now a misfit that must sink. Use sift-down, not sift-up.
sift-down(0) (min-heap: swap with the smaller child while it beats the parent). $i = 0$ : $ℓ = 1, r = 2$ ; $A [ℓ] = 2$ , $A [r] = 5$ . Smallest of ${7, 2, 5}$ is $2$ at idx 1. $2 < 7$ → swap → [2,7,5,8,9], $i = 1$ . Why? The smaller child must rise so both new siblings obey the min-rule.
Now $i = 1$ : $ℓ = 3, r = 4$ ; $A [ℓ] = 8$ , $A [r] = 9$ . Smallest of ${7, 8, 9}$ is $7$ (the node itself) → no swap → stop.

Verify: [2,7,5,8,9]: $2 \leq 7, 5$ ; $7 \leq 8, 9$ . ✓ This is the min-heap column, "increase a key" row of the grid — the case that trips people who assume every key-change is a sift-up.

Ex 12 — Case L: decrease-key on a MAX-heap (it sinks — sift-down)

Worked example Max-heap

[40, 30, 20, 10, 5], decrease index 0 (value 40) to 12 Forecast: lowering the root of a max-heap — climb or sink? Which primitive?

Steps.

Set $A [0] = 12$ : [12,30,20,10,5]. ( $12 \leq 40$ , a decrease.) Why? A smaller value no longer belongs at the top of a max-heap — the large end is the root, so 12 must sink. Use sift-down, not sift-up.
sift-down(0) (max-heap: swap with the larger child while it beats the parent). $i = 0$ : $ℓ = 1, r = 2$ ; $A [ℓ] = 30$ , $A [r] = 20$ . Largest of ${12, 30, 20}$ is $30$ at idx 1. $30 > 12$ → swap → [30,12,20,10,5], $i = 1$ . Why? The larger child rises so both new siblings obey the max-rule.
Now $i = 1$ : $ℓ = 3, r = 4$ ; $A [ℓ] = 10$ , $A [r] = 5$ . Largest of ${12, 10, 5}$ is $12$ (the node itself) → no swap → stop.

Verify: [30,12,20,10,5]: $30 \geq 12, 20$ ; $12 \geq 10, 5$ . ✓ This completes the 2×2 grid: max-heap column, "decrease a key" row — the mirror of Ex 11.

Ex 9 — Case I: a real-world priority queue (word problem)

Worked example A hospital ER assigns each patient an

urgency score; higher = treated first. Patients arrive with scores $60, 20, 80$ . Then the most urgent is treated (removed). Then a new patient arrives with score $90$ . Model this with a max-heap and give the state after each event. Forecast: which event is an insert and which is an extract-max? Predict the final root.

Steps.

Insert 60 → [60]. Insert 20 → append then sift-up: [60,20] ( $20 < 60$ , no swap). Insert 80 → append [60,20,80], $parent (2) = 0$ , $80 > 60$ → swap → [80,20,60]. Why? Each arrival is an Priority Queue insert.
Treat most urgent = extract-max: save 80; move last (60) to root [60,20], $n = 2$ ; sift-down(0): child $A [ℓ] = A [1] = 20$ , $60 > 20$ , no swap. Heap [60,20]. Patient 80 treated. Why? "Treat the most urgent" = remove the maximum.
New patient 90 arrives = insert: append [60,20,90], $parent (2) = 0$ , $90 > 60$ → swap → [90,20,60].

Verify: final heap [90,20,60], root $= 90$ . Order treated so far: 80. Next to be treated: 90. Sanity: the person with the highest score currently waiting (90) is at the root, as a priority queue promises. ✓

Ex 10 — Case J: exam twist — "Is this array a valid max-heap?"

Worked example Is

A = [50, 30, 60, 10, 5] a valid max-heap? If not, name the violation and fix it with one sift-down. Forecast: scan parent–child pairs; guess whether any parent is smaller than a child.

Steps.

List parents (indices $0$ to $⌊ n /2 ⌋ - 1 = ⌊ 5/2 ⌋ - 1 = 1$ , i.e. indices 0 and 1). Why only these? Indices $\geq ⌊ n /2 ⌋$ are leaves — they have no children to violate.
Index 0 (50): children $A [ℓ] = A [1] = 30$ , $A [r] = A [2] = 60$ . Is $50 \geq 60$ ? No → violation at the root. Why this matters? One counterexample is enough to say "not a heap."
Fix with sift-down(0): largest of ${50, 30, 60}$ is 60 ( $r = 2$ ). Swap → [60,30,50,10,5], $i = 2$ . Children of 2 are $ℓ = 5, r = 6$ ≥ $n$ → none → stop.

Verify: original was invalid; repaired heap [60,30,50,10,5]: $60 \geq 30, 50$ ; $30 \geq 10, 5$ . ✓ Note we only had to check up to index $⌊ n /2 ⌋ - 1$ — the leaf-shortcut that makes build-heap efficient, and that distinguishes a heap from a Binary Search Tree (which orders all nodes left-to-right, not just parent-to-child).

Recall One-line summary of the whole matrix

Every heap operation is sift-up (insert, or a key-change toward the root end) or sift-down (extract, repair, or a key-change toward the leaf end), applied over at most one root-to-leaf path of length $lo g_{2} n$ — with zero-work and single-child / empty boundary cases you must guard explicitly with $ℓ < n$ and $r < n$ . The four key-change flavours form a clean 2×2 grid: sift-up for decrease-in-min / increase-in-max, sift-down for increase-in-min / decrease-in-max.