Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 12
Heaps and Priority Queues (Lecture 12)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
In a min-heap, which statement is always true?
That is the heap property, and it is all a heap promises. The array is not sorted (a): Q itself is
[1, 5, 3, …]. Siblings are unordered (c). The largest value is in some leaf, not necessarily the last one (d). -
With 0-based indices, the left child of index i is at:
2i + 1; the right child is 2i + 2 (d). 2i (a) is the 1-based formula of CLRS.
-
The parent of index 10 is at index:
(10 – 1) // 2 = 4. Check: the children of 4 are 9 and 10.
-
The height of a heap holding 1,000 values (a single node has height 0) is:
⌊ log2 1000 ⌋ = 9: levels 0 to 9 hold up to 1,023 nodes. 10 (a) is the number of levels.
-
Which array is a valid min-heap?
3's children are 7 and 4; 2 has none. In (b), 2 at index 3 is below its parent 3; in (c), 1 is below 2; in (d), 3 at index 3 is below 4.
-
Q.push(2): how many swaps does the sift-up make?2 is appended at index 9, under 6 (index 4): swap. Now at index 4, under 5 (index 1): swap. Under 1 at the root: stop. The array becomes
[1, 2, 3, 8, 5, 4, 9, 11, 10, 6]. -
Q.pop()returns 1. Which value is at the root afterwards?10, the last item, moves to the root; its children are 5 and 3, so it swaps with 3, then with 4. The array is
[3, 5, 4, 8, 6, 10, 9, 11]. The new root is always the smaller of the old root's two children. -
Sift-down swaps an item with the better of its two children, not just any child that beats it, because:
Swapping with a child that beats the item but not its sibling puts a larger value above a smaller one (W12-B2). (b) is wrong: sift-down never changes the shape.
-
heapifyon an array of n values sifts down first at index:n // 2 – 1 is the last index with a child; everything after it is a leaf, already a heap of one.
-
The worst-case cost of
heapifyon n values is:At most about n swaps and 2n comparisons (W12-E3).
-
heapifycosts less than n pushes because:Half the nodes are leaves (no work), a quarter move at most one level, and so on: Σ h · n/2h+1 ≤ n. It does look at every value (a) — it just does little with most of them.
-
Pushing the values n, n – 1, …, 2, 1 (in that order) into an empty min-heap costs, in total:
Each new value is the smallest so far and climbs to the root: about log2 i swaps for the i-th push, Θ(n log n) in total. On random input the pushes average about two comparisons each.
-
peek()on a heap of n values costs:The best value is at index 0.
-
Checking whether an arbitrary value x is in a heap of n values costs, in the worst case:
The heap property says nothing about where a value that is not the best might be — it could be in any subtree. Only the root is cheap to find.
-
A heap is stored in an array, with no node objects, because:
Complete shape means indices 0 … n – 1 with no holes, and 2i + 1, 2i + 2, (i – 1) // 2 replace
left,rightandparent. -
enqueue("a", 2),enqueue("b", 1),enqueue("c", 1), then threedequeue()s return:b and c both have priority 1; b was enqueued first (counter 1 against 2), so it is served first. Then c, then a.
-
PriorityQueuepushes(priority, counter, item)rather than(priority, item)because:With
(1, item_b)against(1, item_c), Python compares the items: dictionaries raiseTypeError, strings silently order alphabetically. The unique counter decides every tie before the item is reached. -
The k largest of n values, found with a min-heap of at most k values, cost:
n values, each costing at most one
peekand a pop + push on a heap of k: O(n log k). (c) is sorting everything. -
To find the k largest values you keep a min-heap of size k because:
The root is the smallest of the k kept, and it is the one a new, larger value must replace.
-
The extra space of heap sort (Week 10) is:
Heap sort builds the heap inside the input array and moves each maximum into the space the heap gives up.
-
Heap sort sorts into ascending order with a max-heap because:
The sorted region grows from the right as the heap shrinks from the right. Heap sort is not stable (b).
-
After
MaxHeap([3, 1, 4, 1, 5, 9, 2, 6]), the value at_items[1]is:heapifygives[9, 6, 4, 1, 5, 3, 2, 1]:_items[1]is 6.
18 marks
Written questions
5 written questions (18 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 18
-
Define a binary heap by its two properties. Explain why the shape property matters: what it gives the height, and what it gives the storage.
Model answer and marking points
- Shape: a complete binary tree — every level full except possibly the last, which is filled from the left.
- Order (heap property): every parent beats its children — ≤ in a min-heap, ≥ in a max-heap. So the best value is at the root. Siblings are unordered.
- Height: a complete tree of n nodes has height ⌊ log2 n ⌋, so every operation that walks one path is O(log n). A heap can never degenerate into a list, unlike an unbalanced BST.
- Storage: level-by-level numbering fills indices 0 … n – 1 with no gaps, so the tree is an array; children at 2i + 1 and 2i + 2, parent at (i – 1) // 2. No nodes, no references.
-
Describe
pushandpopon a min-heap, including sift-up and sift-down, the cost of each, and the special cases the code must handle.Model answer and marking points
- push(x): append x at index n (the only place that keeps the shape complete), then sift up: while x beats its parent, swap them. At most one swap per level: O(log n).
- pop(): raise
IndexErrorif empty. Save the root; remove the last item; if the heap is now empty, return it (the one-item case); otherwise put it at the root and sift down: find the better of the item and its (up to two) children; if a child is better, swap and continue. At most two comparisons per level: O(log n). - Special cases: empty
pop/peek; a single item; a node with a left child but no right child (check each child index againstlenbefore reading it). peekis O(1): the root.
-
Explain how
heapifybuilds a heap bottom-up, why it must go from the last parent backwards, and show that it is O(n). Why are n pushes O(n log n) in the worst case?Model answer and marking points
- Algorithm: leave the values in place; for i from
n // 2 − 1down to 0, sift down i. Leaves (the back half) are heaps already. - Why backwards: when i is sifted down, both of its subtrees must already be heaps — sift-down only repairs a root sitting on two valid heaps. Going backwards guarantees that; going forwards does not (W12-K3).
- O(n): a node of height h moves at most h levels, and at most ⌈ n / 2h+1 ⌉ nodes have height h, so the work is at most Σh h · n/2h+1 = n/2Σh h/2h = n/2· 2 = n swaps.
- n pushes: a push costs the node's depth, and half the nodes are at the bottom, at depth ≈ log2 n: in the worst case (descending input for a min-heap) the total is Θ(n log n). Measured in Lecture 12: 2.0 comparisons per element for heapify against 14 per element for pushes, at n = 2^16^.
- Algorithm: leave the values in place; for i from
-
Compare four ways to implement a priority queue — unsorted array, sorted array, binary heap, balanced binary search tree — by the cost of enqueue, dequeue and peek. Which would you choose, and why?
Model answer and marking points
enqueue dequeue peek unsorted array O(1) amortised O(n) O(n) sorted array O(n) O(1) (from the end) O(1) binary heap O(log n) O(log n) O(1) balanced BST O(log n) O(log n) O(log n), or O(1) with a pointer to the minimum - Choose the heap: a workload of n enqueues and n dequeues costs O(n log n), against O(n2) for either array; it lives in one array with no references, and needs no balancing. The BST matches the Big-O but costs nodes, references and a balancing scheme — worth it only if you also need to search for or delete arbitrary items.
-
PriorityQueuestores(priority, counter, item). What goes wrong with(priority, item)? What does the counter add besides avoiding that error?Model answer and marking points
- With
(priority, item), two equal priorities make Python compare the items. Items that do not support<(dictionaries, most objects) raiseTypeError; items that do (strings) are ordered by value, which is not what anyone asked for. - The counter is unique and sits before the item, so every comparison is settled by priority or counter and never reaches the item.
- It also makes ties FIFO: the counter grows with each enqueue, so of two equal priorities the earlier one is served first. A heap on its own is not stable, so this fairness comes only from the counter.
- With