§3Exercises
Ten exercises in four layers: three proofs, two designs, three implementations with milestones, and two read-the-code. Proofs and designs are the same in both languages; the implementation exercises come as templates in PythonJava with tests that fail on purpose, and your job is to make every test pass. Try each exercise before you open its solution.
| # | Layer | Topic | Video |
|---|
| 1 | Proof | The shape of a heap: index formulas, height, leaves | 2 |
| 2 | Proof | Bottom-up construction costs less than 2n comparisons | 3 |
| 3 | Proof | Heap sort is not stable; a lower bound for any comparison sort | 4 |
| 4 | Design | The k largest items of a stream | 1, 2 |
| 5 | Design | Merging k sorted lists | 1, 2 |
| 6 | Implement | A min-heap: up-heap and down-heap | 2 |
| 7 | Implement | A priority queue with a custom order and first-in-first-out ties | 1 |
| 8 | Implement | Heap sort in place | 3, 4 |
| 9 | Read the code | An AI-written heap that "works" | 2 |
| 10 | Read the code | An AI-written down-heap that "keeps the heap property" | 2 |
PROOFS
Exercise 1 · The shape of a heap. A heap with n entries is a complete binary tree stored in an array a[0 … n−1]: the levels are stored one after the other, level d (the root has depth 0) is full unless it is the last one, and the last level is filled from the left. (a) Prove that level d occupies the indices 2ᵈ − 1 … 2ᵈ⁺¹ − 2, and that the children of the entry at index j are at 2j + 1 and 2j + 2, and its parent at ⌊(j − 1) / 2⌋ (j ≥ 1). (b) Prove that the height of the heap (in edges) is ⌊log₂ n⌋. How many levels does a heap of 1,000 entries have, and one of 1,000,000? (c) Prove that the internal entries are exactly a[0 … ⌊n/2⌋ − 1], so a heap has ⌈n/2⌉ leaves, and that the last internal entry is at index (n − 2) / 2 (integer division). Find it for n = 10 and check it against video 3. (d) Many textbooks number the entries from 1. Give the formulas for children and parent in that case, and explain what goes wrong if you use them on a 0-based array (Python and Java behave differently for the parent of the root: how?).
Solution
(a) Depth 0 has 1 = 2⁰ entry and a full level d has 2ᵈ entries, so the levels before level d hold 1 + 2 + … + 2ᵈ⁻¹ = 2ᵈ − 1 entries and level d starts at index 2ᵈ − 1 and ends at 2ᵈ⁺¹ − 2 (every level but the last is full). Number the entries of level d from the left: the entry at index j has position p = j − (2ᵈ − 1). The entries of level d + 1 come in pairs below the entries of level d, in the same left-to-right order, so its children are the positions 2p and 2p + 1 of level d + 1, which are the indices (2ᵈ⁺¹ − 1) + 2p and (2ᵈ⁺¹ − 1) + 2p + 1. Substituting p = j − 2ᵈ + 1: (2ᵈ⁺¹ − 1) + 2j − 2ᵈ⁺¹ + 2 = 2j + 1, and the right child is 2j + 2. For the parent, a child c ≥ 1 is 2j + 1 or 2j + 2 for exactly one j, and ⌊(2j + 1 − 1) / 2⌋ = j = ⌊(2j + 2 − 1) / 2⌋, so the parent is ⌊(c − 1) / 2⌋. ∎
(b) By (a) the entry at index i has depth d exactly when 2ᵈ ≤ i + 1 ≤ 2ᵈ⁺¹ − 1, i.e. d = ⌊log₂(i + 1)⌋. The height is the depth of the last entry, index n − 1, so it is ⌊log₂ n⌋. For n = 1,000 it is 9, i.e. 10 levels; for n = 1,000,000 it is 19, i.e. 20 levels (the numbers of video 2).
(c) An entry j is internal when its left child exists: 2j + 1 ≤ n − 1, i.e. j ≤ (n − 2) / 2, i.e. j ≤ ⌊n/2⌋ − 1 (for n ≥ 2). So the internal entries are exactly 0 … ⌊n/2⌋ − 1, there are ⌊n/2⌋ of them and n − ⌊n/2⌋ = ⌈n/2⌉ leaves; the last internal entry is ⌊n/2⌋ − 1 = (n − 2) / 2. For n = 10 it is 4 (internal 0–4, leaves 5–9): video 3 starts at "last internal node 4". (Checked for all n < 2,100 in test_ex8_claims.py.)
(d) 1-based: the children of j are 2j and 2j + 1 and the parent is ⌊j / 2⌋. On a 0-based array these formulas treat index 0 as its own child (2·0 = 0) and the pair (2j, 2j + 1) is shifted by one: the entry at index 2 is never a child of the root. That is Exercise 9. The parent of the root with the 0-based formula (j − 1) / 2: in Python (0 - 1) // 2 is −1 (floor division), and items[-1] is the last entry: no error, a silent wrong answer; in Java (0 - 1) / 2 is 0 (integer division rounds toward zero): the root becomes its own parent. Test for j = 0 explicitly (our parent(0) throws).
Exercise 2 · Bottom-up construction is O(n). The height of an entry is the longest downward path to a leaf (leaves have height 0). Let S(n) be the sum of the heights of all entries of a heap with n entries. (a) Show that S(n) = ⌊n/2⌋ + S(⌊n/2⌋) for n ≥ 2 (and S(0) = S(1) = 0). (Hint: remove all the leaves; what is left, and what happened to the heights?) (b) Conclude that S(n) = ⌊n/2⌋ + ⌊n/4⌋ + ⌊n/8⌋ + … ≤ n − 1. Compute S(10) and check that it matches the ten entries of video 3. For a perfect heap with n = 2ᵏ⁺¹ − 1 entries show that S(n) = n − log₂(n + 1). (c) Sinking an entry of height h takes at most h swaps and at most 2h comparisons. Conclude that building a heap bottom-up from n entries takes fewer than 2n comparisons and fewer than n swaps. How does that fit the 12 comparisons of video 3 (n = 10)? (d) Inserting the n entries one by one costs one up-heap per entry; give an input (ordering) for which this is Θ(n log n) and explain why that does not contradict (c).
Solution
(a) Remove all the leaves of a heap with n ≥ 2 entries. By Exercise 1(c) the leaves are the indices ⌊n/2⌋ … n − 1, so what is left is a[0 … ⌊n/2⌋ − 1]: again a complete tree, with ⌊n/2⌋ entries. Every remaining entry has its height decreased by exactly 1 (its longest downward path ends in a leaf at the bottom; the entry just above that leaf is still there and has become a leaf of the smaller tree, and no new longer path appeared). The removed leaves had height 0, and each of the ⌊n/2⌋ remaining entries had one more than in the smaller tree. So S(n) = ⌊n/2⌋ + S(⌊n/2⌋). ∎
(b) Unrolling, S(n) = ⌊n/2⌋ + ⌊n/4⌋ + ⌊n/8⌋ + …, a sum with at most ⌊log₂ n⌋ non-zero terms, and ⌊n/2ⁱ⌋ ≤ n/2ⁱ, so S(n) ≤ n(1/2 + 1/4 + … + 1/2ᵐ) = n(1 − 2⁻ᵐ) < n, and since S(n) is an integer, S(n) ≤ n − 1. (The exact value is n minus the number of 1-bits of n: checked for all n < 3,000.) S(10) = 5 + 2 + 1 = 8: the five internal entries have heights 1, 1, 1, 2, 3. For n = 2ᵏ⁺¹ − 1: S(n) = Σₕ h · 2ᵏ⁻ʰ = 2ᵏ⁺¹ − k − 2 = n − (k + 1) = n − log₂(n + 1); n = 7: 4 = 2·1 + 2.
(c) An entry that starts a sink at height h is at height ≤ h − t after t swaps, and an iteration of the loop needs the entry to have a child, i.e. height ≥ 1; so there are at most h iterations, each with at most 2 comparisons (child against child, child against entry) and one swap. Summing over the internal entries: comparisons ≤ 2·S(n) ≤ 2(n − 1) < 2n and swaps ≤ S(n) < n. For video 3 (n = 10, S = 8): ≤ 16 comparisons, measured 12 (the fixes cost 1, 2, 2, 3, 4 comparisons at heights 1, 1, 1, 2, 3, bounded by 2, 2, 2, 4, 6). The decreasing input of video 3 gives 1,982 comparisons for n = 1,000 against the bound 1,998.
(d) Decreasing keys with a min-heap (n, n − 1, …, 1): every new entry is the smallest so far and climbs to the root, a climb of ⌊log₂ k⌋ levels for the k-th insert, in total Σₖ ⌊log₂ k⌋ = n log₂ n − O(n): Θ(n log n) (7,987 comparisons for n = 1,000, 894,481 for 64,000 in video 3). There is no contradiction: (c) bounds the bottom-up method; one-by-one insertion builds a (different) heap in more steps, and for random keys it is only about 2.3 comparisons per entry against about 1.9 (the honest finding of video 3: n log n is only its worst case).
Exercise 3 · Heap sort: stability and a lower bound. A sort is stable if entries with equal keys keep their original relative order. (a) Show that heap sort (the algorithm of video 4: build a max-heap, then repeatedly swap the root with the last entry of the heap, shrink the heap and sink the root; a child moves up only if it is strictly larger) is not stable: find an input with only two entries that shows it. Also check the three-entry example of the video. (b) Show how to make any sort stable by sorting pairs (key, original position). Prove that the output is the stable order, and say what it costs in memory. (c) A comparison sort must be able to produce each of the n! orders. Prove that every comparison sort needs at least ⌈log₂ n!⌉ comparisons in the worst case, compute it for n = 10 (video 4 sorts ten entries with 35 comparisons), and show that log₂ n! ≥ (n/2) log₂(n/2), so ⌈log₂ n!⌉ is of order n log n.
Solution
(a) Two entries (1, a), (1, b) with equal keys. Build: the only internal entry is index 0; its child (1, b) is not strictly larger, so nothing moves. Extraction: swap the root with the last entry: [(1, b), (1, a)]. The equal keys changed places: not stable (checked in test_ex8_claims.py). Video 4's example [(2, a), (2, b), (1, c)] gives (1, c), (2, b), (2, a): the 2s are reversed. Heap sort throws the original order away because the swap of the root with the last entry jumps over every entry in between.
(b) Replace every entry x with the pair (x.key, i), where i is its original position, and sort the pairs lexicographically. Distinct pairs have a strict total order, so the sorted sequence is unique; pairs with equal keys appear in increasing i, which is their original order. So the output is exactly the stable order, whatever (unstable) algorithm sorts the pairs. The cost: n extra integers, O(n) memory, and the in-place advantage is gone.
(c) A comparison sort is a binary decision tree (each inner node one comparison, each leaf one output order). To be correct it needs a leaf for each of the n! input orders, and a binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n! and the worst case needs h ≥ ⌈log₂ n!⌉ comparisons. n = 10: 10! = 3,628,800, log₂ = 21.79, so at least 22; the heap sort of video 4 used 35 on its input (more than the bound, as it must be; we also checked all 8! inputs for n = 8 against ⌈log₂ 8!⌉ = 16). Lower bound of order n log n: the largest ⌈n/2⌉ factors n, n − 1, …, ⌊n/2⌋ + 1 of n! are each ≥ n/2, so n! ≥ (n/2)^(n/2) and log₂ n! ≥ (n/2) log₂(n/2), which is of order n log n. So heap sort, merge sort and quicksort are optimal up to a constant factor.
DESIGNS
Exercise 4 · The k largest items of a stream. Items arrive one at a time; there are too many to store, but you must be able to report the k largest at any moment (k is small, say 10 or 1,000). (a) Design the algorithm with a heap of at most k entries. Which kind of heap (min or max) do you use and why? What do you do with a new item? (b) Give the cost in comparisons per item and in total for n items (a bound in terms of n and k) and the memory. Trace it on the stream 5, 1, 9, 3, 7, 8, 2 with k = 3 and write the heap after every item. (c) Compare with (i) sorting the whole stream, (ii) a max-heap of all n items followed by k removals, (iii) keeping a sorted list of size k. When is each better?
Solution
(a) Keep a min-heap of the k largest items seen so far: its root is the smallest of the k, the one that must be beaten. A new item x: if the heap has fewer than k entries, insert x. Otherwise compare x with the root; if x is not larger, ignore it; if it is larger, remove the root and insert x (one heapreplace: put x at the root and sink it). The answer is the contents of the heap (sort them if you want them in order). A max-heap would put the largest on top, which tells you nothing about which entry to throw away.
(b) Per item: 1 comparison with the root, and when it is larger at most 2⌊log₂ k⌋ more for the down-heap, so at most 1 + 2⌊log₂ k⌋ per item and O(n log k) in total (plus O(k) or O(k log k) to fill the heap at the start); memory O(k), one pass. Trace (k = 3), heap in array order after each item: 5 → [5]; 1 → [1, 5]; 9 → [1, 5, 9]; 3 > 1, replace the root → [3, 5, 9]; 7 > 3 → [5, 7, 9]; 8 > 5 → [7, 8, 9]; 2 ≤ 7, ignored → [7, 8, 9]. The three largest are 9, 8, 7 (checked in test_ex8_claims.py, also in Java).
(c) (i) Sorting the whole stream: O(n log n) time and O(n) memory, and it needs the whole stream: no good for k ≪ n or an endless stream. (ii) A max-heap of all n items, then k removals: O(n + k log n) time but O(n) memory. (iii) A sorted list of size k: the same O(n) comparisons for the common case "x is too small" but O(k) to insert, so O(nk) in the worst case: better only for tiny k. When k is close to n, sorting is simpler and just as good.
Exercise 5 · Merging k sorted lists. You have k lists, each already sorted, N items in total (think of k sorted log files). (a) Design a merge that outputs the N items in sorted order using a heap that never holds more than k entries. What is an entry, what does the heap compare, and what do you do after each removal? (b) Give the time in terms of N and k, and the extra memory. Trace it on [1, 4, 9], [2, 3, 10, 11], [], [0, 5] and count the removals. (c) Why is "merge the first two lists, then merge the result with the third, …" worse (give its cost for k lists of equal length)? What if you merge the lists in pairs, like merge sort?
Solution
(a) An entry is (value, list number, position in the list): the value is the front item of one list. The heap compares by value (break ties by list number so the merge is deterministic and stable across lists). Put the first entry of every non-empty list into the heap (at most k entries). Repeat: remove the smallest entry, output its value, and if its list has a next item put that item's entry into the heap. At every moment the heap holds exactly one entry for each list that is not finished, so it never holds more than k.
(b) Every item is inserted once and removed once, each in O(log k) (the heap has at most k entries): O(N log k) time and O(k) extra memory (besides the output). Trace for [1, 4, 9], [2, 3, 10, 11], [], [0, 5]: the heap starts with 1, 2, 0 (the empty list contributes nothing); the removals give 0 (then 5 enters), 1 (4), 2 (3), 3 (10), 4 (9), 5 (list 4 is finished), 9 (list 1 is finished), 10 (11), 11: 9 removals = N, and the heap never exceeded 3 entries.
(c) Merging the result so far with the next list costs the length of both: with k lists of m items each, the j-th merge handles (j + 1)m items, in total about k²m/2 = O(Nk), far worse than N log k when k is large. Merging in pairs like merge sort (k/2 pairs, then k/4, …) takes log₂ k rounds of N items each: O(N log k) too, but it needs a whole new list per round (O(N) memory) and all lists available; the heap streams the output with O(k) memory (Python's heapq.merge does exactly this).
IMPLEMENTATIONS (WITH MILESTONES)
Each file lists its milestones at the top. Do them in order and run the tests after each one.
Exercise 6 · A min-heap — ex8_heap.pyEx8Heap.java. Implement the index formulas (the root has no parent!), insert with up-heap, then peek and remove_min with down-heap, counting comparisons and swaps like the videos. The tests replay the seven inserts and seven removals of video 2 with their exact counts, compare random operations with a sorted list and check the cost of 1,000 increasing and 1,000 decreasing inserts (999 and 7,987 comparisons).
Solution
Reference: solutions/py/ex8_heap.py, solutions/java/Ex8Heap.java. The points to get right: parent(0) must raise (Exercise 1(d)); the up-heap stops when x is not smaller than its parent, and that last test also counts as a comparison (inserting 1, 2, …, 1,000 in increasing order costs exactly 999 comparisons: every insert but the first makes one test and no swap); the down-heap compares the children only when both exist, then the smaller child with the sinking entry; use < strictly so equal entries do not move; remove the last entry before putting it at the root, so the size is right when the sinking starts. The counts of the tests are the numbers of video 2: the seven inserts cost 9 comparisons and 6 swaps, remove_min of the minimum 2 costs 3 comparisons and 1 swap.
Exercise 7 · A priority queue with a custom order — ex8_pq.pyEx8Pq.java. Wrap a heap (yours, heapq or PriorityQueue) in an interface with insert(priority, value), min, remove_min, a custom order (a key function / a Comparator, so a max-queue is one line), and first-in-first-out among equal priorities, which the standard libraries do not promise (video 1 shows a c e b d and a e d c b). Values are never compared.
Solution
Reference: solutions/py/ex8_pq.py, solutions/java/Ex8Pq.java. Entries are stored as (key(priority), sequence number, priority, value) in Python and as (entry, sequence number) with a comparator that compares the order first and the sequence number second in Java. Because the sequence number is unique, two entries are never equal, so (1) the heap never falls through to comparing the values (Python: heapq.heappush(h, (1, {"job": "a"})) twice raises TypeError, as in video 1) and (2) equal priorities come out in insertion order: a strict total order has exactly one sorted order, and sorting by (key, sequence number) is the stable sort of the priorities. A max-queue is key=lambda p: -p (Python) or Comparator.reverseOrder() (Java); for priorities that cannot be negated, use a wrapper class or a comparator. Without the counter, heapq with a class that compares priorities only gave a c e b d in video 1 and java.util.PriorityQueue gave a e d c b: ties are unspecified, and the two libraries differ.
Exercise 8 · Heap sort in place — ex8_heapsort.pyEx8HeapSort.java. Write down_heap, build_max_heap and heap_sort, each returning the number of comparisons it made. The tests check the counts of video 4 (9 comparisons to build the heap of ten entries, 35 for the whole sort), that the build never needs 2n comparisons, that the list is sorted in place (Python: a memory check) and equal keys do not move in a down-heap.
Solution
Reference: solutions/py/ex8_heapsort.py, solutions/java/Ex8HeapSort.java. down_heap(a, j, n) is the same loop as in Exercise 6 but with the opposite comparison and the heap boundary n instead of len(a): the sorted suffix a[n:] must not be touched. Counts: building the heap of the ten entries 20, 16, 9, 12, 5, 8, 3, 14, 6, 11 costs 9 comparisons and gives 20, 16, 9, 14, 11, 8, 3, 12, 6, 5; the whole sort costs 35 (video 4). The build loop starts at the last internal entry (n - 2) // 2 (Exercise 1(c)) and goes down to 0; the extraction loop runs for end = n − 1 … 1 (the last remaining entry is already in place) and swaps before it sinks the new root in a[0 … end − 1]. Common mistakes: sinking in a[0 … end] (the sorted entry gets pulled back into the heap), >= instead of strict > (equal entries swap for nothing and the counts change), a call of sorted()/list.sort() (no longer in place). The memory test of the Python template allocates less than 20,000 bytes for a list of 20,000 entries, where a copy would need about 160,000.
READ THE CODE
An AI assistant wrote each class together with a claim. In both exercises the claim is wrong because of a bug. Find a small input that shows it (compare repeated remove_min with the sorted input), say what exactly goes wrong and why small examples do not show it, and fix it. Use the habits from the chapter: compare with sorted(), check the heap property after every operation, test with more than three entries.
Exercise 9 — Heap9 in read/py/ex8_read.py / Ex8Read.Heap9 in read/java/Ex8Read.java. The comment claims that insert and remove_min are correct and take O(log n).
Solution
The bug. insert uses the 0-based parent formula (j − 1) // 2, but remove_min sinks along the 1-based child formulas 2j and 2j + 1 (copied from a textbook that numbers from 1). The two halves disagree about the tree: insert believes the children of index j are 2j + 1 and 2j + 2, remove_min looks at 2j and 2j + 1. At the root the "children" are indices 0 (the root itself) and 1, so the real right child, index 2, is never compared with the root; one level below, the children of index 1 are looked up at 2 and 3 instead of 3 and 4, and so on. The sinking entry therefore stops, or turns, too early and a larger entry stays above a smaller one: the list stops being a heap.
A small input. Insert 1, 3, 2, 4 (the list is [1, 3, 2, 4]) and call remove_min four times: the calls return 1, 3, 2, 4 instead of 1, 2, 3, 4. After the first call the list is [3, 2, 4]: the root 3 is larger than its child 2. With seven entries, 1, 5, 2, 6, 7, 3, 4 and one remove_min, the list is [4, 5, 2, 6, 7, 3]: the new root 4 was compared only with index 1 (5), never with index 2 (2), and the next call returns 4 although 2 is smaller; the whole sequence comes out 1, 4, 3, 5, 2, 6, 7.
Why small examples do not show it. For every order of 1, 2 or 3 entries the code is correct (we tried all 1 + 2 + 6 orders): after the first removal there are at most two entries, and then comparing the root with index 1 is all there is to do. From four entries on it fails: for 4 entries on 8 of the 24 input orders, for 5 on 24 of 120, for 7 on 3,732 of 5,040. A test with the textbook example of three entries passes; a random test against sorted() with more than three entries finds it at once (test_ex8_read.py).
The claim. "O(log n)" is true (the loop runs at most about log₂ n times) but correctness is not: an algorithm that is fast and wrong is not a heap. The fix: children 2j + 1 and 2j + 2 and the loop condition 2j + 1 < n. The Java class Ex8Read.Heap9 has the same bug ((j - 1) / 2 is fine for j ≥ 1, the children are 2 * j and 2 * j + 1) and the same numbers.
Exercise 10 — Heap10 in read/py/ex8_read.py / Ex8Read.Heap10 in read/java/Ex8Read.java. The comment claims that remove_min sinks the new root along the smaller child so the list is a heap again.
Solution
The bug. The index formulas are right this time, but the code only looks at the left child: it swaps with it whenever it is smaller than the sinking entry and never looks at the right child. The comment says "smaller child"; the code says "left child". Two things go wrong: the right child can be smaller than the left one (the entry should go there), so the smaller of the two ends up below a larger one; and the loop can stop because the left child is not smaller although the right child is.
A small input. Insert 1, 3, 2, 4 and remove the minimum: the new root 4 is compared with its left child 3 and swapped: [3, 4, 2]; the right child 2 is smaller than the new root 3 and no one ever looked at it. The four calls return 1, 3, 2, 4 instead of 1, 2, 3, 4. With seven entries 1, 5, 3, 6, 7, 4, 8 and one remove_min the list is [5, 6, 3, 8, 7, 4]: the root 5 is larger than its right child 3, and the calls return 1, 5, 4, 6, 7, 3, 8.
Why small examples hide it. With at most three entries, after the removal there are at most two entries and the root has at most one child: no choice to make, the "left child" is the smaller child. From four entries on it fails: 8 of the 24 orders of four entries, 60 of 120 for five, and every one of the 5,040 orders of seven entries (so even sorted input shows it: 1, 2, 3, 4, 5 returns 4 before 3). The fix: pick the smaller of the two children, comparing them first when both exist (as ArrayHeap.down_heap in the chapter code does: one comparison between the children, one between the smaller child and the entry). Always test a heap against sorted() with random input of more than three entries and assert the heap property after every operation.