Chapter 6 · Transform-and-Conquer
Heap Lab
A heap is a tree that lives inside an array: the children of position i sit at 2i and 2i + 1, and its parent sits at ⌊i/2⌋. Build one, pull the root out of it, and sort with it, watching both views move together.
Heap type
key being placed (v)
being compared
just moved
settled / sorted
not in the heap yet
How to read this
- Two views, one heap
- The top drawing is the tree; the row of boxes underneath is the array H[1..n] that actually stores it. The small number on each tree node is its array index, so you can match them. Position 0 is left unused so the index arithmetic stays clean: parent of i = ⌊i/2⌋, children of i = 2i and 2i + 1.
- Parental dominance
- In a max-heap every parent is ≥ its children, so the largest key is at the root. Flip the toggle to a min-heap and every comparison flips: parents are ≤ children and the smallest key rises to the top.
- Colors
- Blue is the key v being sifted, yellow marks the keys being compared, red marks the pair that just traded places, green marks keys that are settled (in heapsort: already in their final sorted place), and gray marks array slots that are not part of the heap yet.
- Counters
- “Comparisons” counts key comparisons exactly as the pseudocode makes them: one to pick the bigger child (only when there are two children) and one to test v against it. Bottom-up construction never needs more than 2n of them (Levitin §6.4).
Try this
- Book check. Run bottom-up construction on 2, 9, 7, 6, 5, 8. You should end with 9, 6, 8, 2, 5, 7 after 7 comparisons, well under 2n = 12.
- Bottom-up vs top-down. Load 1, 2, 3, …, 15 (sorted, max-heap). Bottom-up needs 22 comparisons; top-down needs 34, because every new key climbs all the way to the root. Now try 15, 14, …, 1: both methods need only 14 comparisons. Why is an already-sorted-descending array so cheap for both?
- Heapsort's two stages. Run heapsort on 2, 9, 7, 6, 5, 8 and write down the array after each root deletion. The green tail should grow as 9 | 8, 9 | 7, 8, 9 | … until the array is sorted.
- Priority queue. In the playground, insert 10 into the book heap. Predict how many levels it rises before you press play (it becomes the new root). Then delete the root three times: the keys come out in decreasing order.
- Min-heap. Toggle min-heap and run heapsort. The array now ends up in decreasing order. Explain why in one sentence.