Algorithms from zero
Heaps: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes the heap mental model stick.
Reconstruct the unit’s spine without looking back: the two-part heap invariant, the O(n) build-heap argument, the PQ contract, the size-k heap pattern for top-k and k-way merge, and how heap-sort falls out of pop.
- 01State the two properties that define a binary heap, and explain why they let you store it as a flat array with no pointers.
- 02Walk through push and pop, and state why each is O(log n).
- 03Why is build-heap O(n) while inserting n elements one-by-one is O(n log n)?
- 04Distinguish the priority-queue ADT from the binary heap, and name when the distinction changes a design.
- 05Explain the size-k heap pattern and how the same idea solves both top-k and k-way merge.
- 06How does heap-sort fall out of the heap operations, and what are its time and space costs?
If you reconstructed each answer from memory, you hold the unit’s spine: the completeness + heap-property pair gives the pointerless array and O(1) peek; sift-up/sift-down give O(log n) push/pop; build-heap reaches O(n) by weighting cost on node height; the PQ contract is separate from the heap that implements it; the size-k heap turns into top-k (min-heap, evict the root) and k-way merge (one candidate per list, advance by index); and heap-sort is just build-heap plus repeated pop, O(n log n) guaranteed, O(1) space.