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

Definition The two repair primitives (self-contained recap)

Every heap operation is built from exactly two moves. Keep this callout open as you work.

sift-up(i) — the node at $i$ is too extreme for its slot and must climb. While $i > 0$ and it beats its parent (max-heap: $A [i] > A [parent (i)]$ ; min-heap: $A [i] < A [parent (i)]$ ): swap with the parent, set $i \leftarrow parent (i)$ . Picture a node rising up one edge at a time toward the root.
sift-down(i) — the node at $i$ is too weak for its slot and must sink. Compare $A [i]$ with its children; pick the child that should be the parent (max-heap: the largest; min-heap: the smallest). If a child beats $A [i]$ , swap and recurse into that child. Picture a node falling down one edge at a time toward a leaf.

Both touch only one root-to-leaf path of length $\leq ⌊ lo g_{2} n ⌋$ ⇒ $O (lo g n)$ .

Level 1 — Recognition

Exercise 1.1 — Is it a heap?

Which of these arrays is a valid max-heap? (a) [9, 7, 8, 3, 6, 5, 2] (b) [9, 7, 8, 3, 6, 9, 10] (c) [10, 9, 8, 7, 6, 5, 4]

Recall Solution

Check $A [parent (i)] \geq A [i]$ for every $i \geq 1$ . The figure draws (a) and (b) as trees; every edge must point from a bigger (or equal) parent down to a smaller child.

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

(a) parents to check: $i = 1$ (parent 0): $9 \geq 7$ ✓; $i = 2$ : $9 \geq 8$ ✓; $i = 3$ (parent 1): $7 \geq 3$ ✓; $i = 4$ : $7 \geq 6$ ✓; $i = 5$ (parent 2): $8 \geq 5$ ✓; $i = 6$ : $8 \geq 2$ ✓. Every edge good (all green in the figure). Valid.

(b) $i = 5$ : parent $(5) = ⌊ 4/2 ⌋ = 2$ , $A [2] = 8$ , child $A [5] = 9$ . $8 \geq 9$ ? No — the red edge in the figure marks a child that outranks its parent. Invalid.

(c) every parent $\geq$ child (it is even fully sorted descending, which is always a valid max-heap). Valid.

Answer: (a) and (c).

Exercise 1.2 — Read the family

In array [50, 30, 40, 10, 5, 20], what are the children and parent of index $2$ ?

Recall Solution

$left (2) = 2 \cdot 2 + 1 = 5$ , $right (2) = 2 \cdot 2 + 2 = 6$ . Index 6 is out of range ( $n = 6$ , valid indices $0..5$ ), so index 2 has one child: $A [5] = 20$ . $parent (2) = ⌊(2 - 1) /2 ⌋ = ⌊ 0.5 ⌋ = 0$ , so parent is $A [0] = 50$ .

Level 2 — Application

Exercise 2.1 — Insert trace

Insert $45$ into the max-heap [40, 30, 20, 10, 5]. Show every swap.

Recall Solution

Append 45 at index $n = 5$ (only legal slot keeping the tree complete): [40,30,20,10,5,45], $i = 5$ . Then sift-up — the yellow node climbs one red edge per step in the figure.

parent $(5) = ⌊ 4/2 ⌋ = 2$ , $A [2] = 20$ . $45 > 20$ → swap → [40,30,45,10,5,20], $i = 2$ .
parent $(2) = 0$ , $A [0] = 40$ . $45 > 40$ → swap → [45,30,40,10,5,20], $i = 0$ . Stop (root).

Result [45,30,40,10,5,20], 2 swaps.

Exercise 2.2 — Extract-max trace

Perform one extract-max on [45,30,40,10,5,20].

Recall Solution

max $= A [0] = 45$ . Move last element (20) to root, shrink to $n = 5$ : [20,30,40,10,5]. Then sift-down — the yellow root sinks down the branch of its larger child (red arrow).

sift-down(0): children $A [1] = 30$ , $A [2] = 40$ . Largest of ${20, 30, 40}$ is $40$ at idx 2. $40 \neq = 20$ → swap → [40,30,20,10,5], $i = 2$ .

$i = 2$ : children idx $5, 6$ out of range → no children → stop.

Returns 45, heap becomes [40,30,20,10,5].

Exercise 2.3 — decrease-key trace (min-heap)

Min-heap [3, 9, 5, 14, 10, 8]. Do decrease-key(4, 1) (lower $A [4] = 10$ to $1$ ).

Recall Solution

Set $A [4] = 1$ : [3,9,5,14,1,8], $i = 4$ . The lowered key is now too small for its slot → sift-up (min-heap: climb while smaller than parent). Watch the yellow node rise in the figure.

parent $(4) = ⌊ 3/2 ⌋ = 1$ , $A [1] = 9$ . Min-heap sift-up: $1 < 9$ → swap → [3,1,5,14,9,8], $i = 1$ .
parent $(1) = 0$ , $A [0] = 3$ . $1 < 3$ → swap → [1,3,5,14,9,8], $i = 0$ . Stop.

Result [1,3,5,14,9,8]; new min = 1 at root.

Level 3 — Analysis

Exercise 3.1 — Build-heap by sift-down

Turn the raw array [3, 9, 2, 1, 4, 5] into a max-heap using bottom-up build-heap (sift-down from index $⌊ n /2 ⌋ - 1$ down to $0$ ). Show each sift-down.

Recall Solution

$n = 6$ , start at $⌊ 6/2 ⌋ - 1 = 2$ , go down to 0. The figure shows the tree at three stages: the raw start, after fixing index 2, and the final max-heap — the yellow node is the one being sifted, red arrows are its swaps, green marks the settled root.

i=2: $A [2] = 2$ ; children idx 5 ( $A [5] = 5$ ), idx 6 (none). Largest $= 5 > 2$ → swap → [3,9,5,1,4,2]. idx 5 has no children → stop.
i=1: $A [1] = 9$ ; children idx 3 ( $A [3] = 1$ ), idx 4 ( $A [4] = 4$ ). Largest of ${9, 1, 4} = 9 = A [1]$ → no swap.
i=0: $A [0] = 3$ ; children idx 1 ( $9$ ), idx 2 ( $5$ ). Largest $= 9$ at idx 1 → swap → [9,3,5,1,4,2], now $i = 1$ . Children idx 3 ( $1$ ), idx 4 ( $4$ ). Largest of ${3, 1, 4} = 4$ at idx 4 → swap → [9,4,5,1,3,2], $i = 4$ , no children → stop.

Max-heap [9,4,5,1,3,2]. Verify: $9 \geq 4, 9 \geq 5$ ; $4 \geq 1, 4 \geq 3$ ; $5 \geq 2$ . ✓

Exercise 3.2 — Counting swaps

For the insert in Exercise 2.1, the value climbed to the root. What is the maximum number of swaps any single insert can perform in a heap of size $n$ , and why?

Recall Solution

A sift-up moves $i$ to its parent each swap, so the number of swaps is bounded by the depth of the inserted leaf, which is the tree height $⌊ lo g_{2} n ⌋$ . After appending, $n$ elements exist, so height $= ⌊ lo g_{2} n ⌋$ . The worst case (new key is the new global max) climbs the full path: $⌊ lo g_{2} n ⌋$ swaps. For $n = 6$ : $⌊ lo g_{2} 6 ⌋ = 2$ — matching the 2 swaps we counted. Answer: $⌊ lo g_{2} n ⌋$ .

Level 4 — Synthesis

Exercise 4.1 — Heapsort trace

Using max-heap extraction, sort [3, 1, 4, 1, 5] ascending. Give (a) the built max-heap, then (b) the array after each extract-max writes the max into the freed tail slot.

Recall Solution

(a) Build-heap on [3,1,4,1,5], $n = 5$ , start at $⌊ 5/2 ⌋ - 1 = 1$ .

i=1: $A [1] = 1$ ; children idx 3 ( $1$ ), idx 4 ( $5$ ). Largest $5$ at idx 4 → swap → [3,5,4,1,1], idx 4 no children → stop.
i=0: $A [0] = 3$ ; children idx 1 ( $5$ ), idx 2 ( $4$ ). Largest $5$ at idx 1 → swap → [5,3,4,1,1], $i = 1$ ; children idx 3 ( $1$ ), idx 4 ( $1$ ); largest $= 3$ → stop.

Built max-heap: [5,3,4,1,1].

(b) Repeated extract-max (swap root with last live slot, shrink, sift-down):

Swap $A [0] \leftrightarrow A [4]$ : [1,3,4,1,5], live size 4. sift-down(0): children $3, 4$ → largest $4$ idx2 → swap [4,3,1,1,|5]. → live [4,3,1,1].
Swap $A [0] \leftrightarrow A [3]$ : [1,3,1,|4,5], size 3. sift-down(0): children idx1 ( $3$ ), idx2 ( $1$ ) → largest $3$ → swap [3,1,1,|4,5]. → live [3,1,1].
Swap $A [0] \leftrightarrow A [2]$ : [1,1,|3,4,5], size 2. sift-down(0): child idx1 ( $1$ ) → equal, no swap.
Swap $A [0] \leftrightarrow A [1]$ : [1,|1,3,4,5], size 1. Done.

Sorted: [1,1,3,4,5]. ✓ (Max-heap extraction places each max at the shrinking tail, so the array ends ascending.)

Exercise 4.2 — Dijkstra decrease-key

A min-heap of (distance) keys is [2, 6, 4, 12, 9, 7] for vertices at those indices. A relaxation finds a shorter path to the vertex at index 3, lowering its key $12 \to 3$ . Do the decrease-key, then one extract-min (as Dijkstra pops the closest vertex).

Recall Solution

decrease-key(3, 3): $A [3] = 3$ → [2,6,4,3,9,7], $i = 3$ .

parent $(3) = 1$ , $A [1] = 6$ . $3 < 6$ → swap → [2,3,4,6,9,7], $i = 1$ .
parent $(1) = 0$ , $A [0] = 2$ . $3 < 2$ ? No → stop. Heap: [2,3,4,6,9,7].

extract-min: min $= 2$ . Move last ( $7$ ) to root, $n = 5$ : [7,3,4,6,9]. sift-down(0):

children $A [1] = 3$ , $A [2] = 4$ . Smallest of ${7, 3, 4} = 3$ at idx1 → swap → [3,7,4,6,9], $i = 1$ .
children $A [3] = 6$ , $A [4] = 9$ . Smallest of ${7, 6, 9} = 6$ at idx3 → swap → [3,6,4,7,9], $i = 3$ . No children → stop.

Returns 2; heap [3,6,4,7,9].

Level 5 — Mastery

Exercise 5.1 — Delete an arbitrary index

Design (and trace) an algorithm to delete the element at an arbitrary index $i$ from a max-heap, in $O (lo g n)$ . Test on [45,30,40,10,5,20] deleting index $2$ (value $40$ ).

Recall Solution

Algorithm: overwrite $A [i]$ with the last element $A [n - 1]$ , shrink $n$ , then restore in whichever direction is now broken: if the moved value is larger than its parent, sift-up(i); otherwise sift-down(i). Only one path is touched → $O (lo g n)$ .

Why can only ONE direction break? Before the deletion the heap was valid, so the parent of slot $i$ was $\geq$ every node in $i$ 's subtree — in particular $\geq$ both of $i$ 's children. Now we drop a single new value $v$ into slot $i$ . Two mutually exclusive cases:

If $v > parent$ : then $v$ is bigger than its parent, but the parent already dominated both children, so $v$ — being even bigger — is also $\geq$ both children. The child-inequalities hold; only the parent-inequality can fail → sift-up.
If $v \leq parent$ : the parent-inequality holds by assumption; the only possible break is $v$ being smaller than a child → only child-inequalities can fail → sift-down. Since " $v > parent$ " and " $v \leq parent$ " cannot both hold, at most one direction is ever violated. That is why a single primitive suffices.

Trace: delete idx 2 from [45,30,40,10,5,20]. Last element $A [5] = 20$ . Overwrite $A [2] = 20$ , $n = 5$ : [45,30,20,10,5].

Compare with parent $(2) = 0$ , $A [0] = 45$ : $20 > 45$ ? No → the " $v \leq parent$ " case → sift-down.
sift-down(2): children idx 5,6 → out of range → no children → stop.

Result [45,30,20,10,5]. (Here 20 already fit both ways, so no swap was needed.)

Exercise 5.2 — Extract-max cost lower bound

Argue that any comparison-based extract-max on a max-heap of $n$ elements must, in the worst case, do $Θ (lo g n)$ comparisons — i.e. $O (lo g n)$ is tight, not pessimistic.

Recall Solution

Upper bound $O (lo g n)$ . After removing the root and promoting the last leaf, sift-down settles the misfit level by level. At each level we must find the largest of three: the node and its two children. That is done with two comparisons — first compare the two children to each other (1 comparison) to find the bigger child, then compare that winner against the node (1 comparison) to decide whether to swap: $\leq 2$ comparisons per level. The path from root to a leaf has $⌊ lo g_{2} n ⌋$ levels, so the total is $\leq 2 ⌊ lo g_{2} n ⌋ = O (lo g n)$ .

Lower bound $Ω (lo g n)$ . The promoted last-leaf value can be the global minimum. To settle it, sift-down must sink it all the way to a leaf, one level per step, doing $\geq 1$ comparison per level. That path has length $⌊ lo g_{2} n ⌋$ , so it costs $Ω (lo g n)$ comparisons in the worst case.

Together: $Ω (lo g n)$ and $O (lo g n)$ ⇒ $Θ (lo g n)$ . So the bound in the parent note's cost table is tight, not merely an over-cautious upper estimate.

Recall Self-test checklist

Can you insert, extract, and decrease-key without peeking? ::: Trace one of each from a fresh random array; check every parent–child inequality at the end. Do you know why build-heap is $O (n)$ not $O (n lo g n)$ ? ::: Most nodes are shallow; the height-weighted sum $\sum_{h} \frac{n}{2 ^{h + 1}} h$ converges to $O (n)$ . Which primitive does min-heap decrease-key use, and why? ::: sift-up — smaller keys belong nearer the root. After arbitrary-delete, why does only one direction break? ::: The old parent dominated the whole subtree; the new value is either above the parent (only parent-inequality can fail) or below it (only child-inequalities can fail) — never both.