Algorithms from zero
Heaps: multiple-choice review
Crux Multiple-choice synthesis across the heaps unit: the heap invariant, O(n) build-heap, the PQ contract, and choosing the right heap for top-k and k-way merge.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. None are definition recall — each is a design decision: which heap, which complexity, which invariant. Pick the answer you would defend in an interview, then read why each distractor fails.
Goal
Confirm you can connect the heap invariant, the O(n) build-heap argument, the priority-queue contract, and the size-k heap pattern that powers both top-k and k-way merge — the synthesis the five lessons built toward.
Quiz
Completed
An interviewer hands you the array [10, 5, 20, 15, 30] and asks 'is this a valid min-heap?' What is the correct answer and the reason?
Heads-up Being unsorted is not the test. A heap must satisfy parent ≤ both children at every node. Here 10 > 5 at the root, so it fails — regardless of sortedness.
Heads-up A min-heap is NOT a sorted array. [1, 3, 2, 5, 4] is a valid min-heap but not sorted. Only the parent-child relationship at each index must hold.
Heads-up The minimum being present is not enough; in a min-heap the minimum must be at the root (index 0). Here the root is 10, not 5.
Quiz
Completed
Building a heap from an n-element array by calling push n times is O(n log n), but the standard build-heap (heapify) is O(n). Where does the speedup come from?
Heads-up build-heap sift-downs every non-leaf — about n/2 nodes. It is not skipping nodes; the win is that nodes near the bottom (the majority) have tiny subtree heights, so each sift-down is cheap.
Heads-up build-heap is provably O(n). The summation Σ (n/2^{h+1})·h converges to a constant times n, so heapify is linear — a standard, well-known result.
Heads-up build-heap is O(n) on ANY input, sorted or not. The bound comes from the height distribution of nodes, which does not depend on the values.
Quiz
Completed
A teammate says 'a priority queue is just a heap.' Why is that imprecise, and when does the distinction earn its keep?
Heads-up It affects real designs. A plain binary heap has no efficient decrease-key, so Dijkstra on dense graphs may want a different PQ implementation. Naming the contract separately from the implementation is what lets you swap it.
Heads-up An ADT has no speed of its own — speed comes from the implementation. A PQ backed by a sorted array has O(n) insert; backed by a heap it is O(log n). The ADT is the contract, not a performance claim.
Heads-up peek in O(1) is exactly a property the heap implementation gives the PQ contract. The PQ ADT specifies peek; the heap is what makes it O(1).
Quiz
Completed
You must keep the k largest elements out of a stream of n numbers (k ≪ n). Which heap, and why that one and not the other?
Heads-up For k LARGEST you want to evict the SMALLEST candidate when the heap overflows. A max-heap hides the minimum, so finding the evictee costs O(k). The min-heap keeps the evictee at the root — that is the whole trick.
Heads-up That is O(n + k log n) time and O(n) space — you stored everything. The size-k min-heap is O(n log k) time and O(k) space, which is the point when k ≪ n and the data is a stream you cannot fully retain.
Heads-up The choice changes the eviction cost from O(log k) (min-heap, evictee at root) to O(k) (max-heap, must scan for the minimum). It is a correctness-of-complexity decision, not style.
Quiz
Completed
In k-way merge of k sorted lists with n total elements, each heap entry stores (value, listIndex, position) rather than just the value. Why carry the bookkeeping?
Heads-up List length is irrelevant to the merge. The bookkeeping exists so that when you remove a head, you can replace it with the next element from that specific list — keeping exactly one candidate per active list.
Heads-up Duplicates merge fine without extra metadata. The metadata's job is advancement: knowing which list to pull the successor from after each pop.
Heads-up The O(n log k) bound comes from the heap holding at most k elements, so each pop/push is O(log k). The metadata is for correctness (advancing the right list), not for the complexity bound.
Quiz
Completed
A pop on a min-heap moves the last array element to the root, shrinks the array by one, then sift-downs. Why move the LAST element up rather than promoting the smaller child into the gap and repeating?
Heads-up The last element has no special rank — it is just the rightmost leaf. It is chosen because removing it preserves the complete-tree shape, then sift-down fixes ordering. It is usually large, which is why it sinks back down.
Heads-up Promoting children is not forbidden by a library; it is avoided because it can violate the complete-binary-tree shape invariant, which the array encoding depends on for its index arithmetic.
Heads-up Only moving the last element preserves the complete-tree shape that the array representation requires (no internal gaps). Promoting children can create a gap that is not at the end, breaking the index formulas.
Recap
The through-line of the unit is one structure earning many jobs. The heap property plus the complete-tree shape give O(1) peek and O(log n) push/pop via sift-up and sift-down; build-heap exploits the height distribution to reach O(n). Wrap that in the priority-queue contract and the same machine becomes a scheduler, a top-k filter (size-k MIN-heap, evict the root), and a k-way merger (one candidate per list, advance by listIndex). Every question here was really ‘which invariant or which heap,’ which is exactly the call you make in an interview or a real system.