Algorithms from zero
Heaps: build a priority queue and merge k streams
Reading about heaps is not the same as having one you trust. Build the binary heap yourself, wrap it as a priority queue, then make it earn its keep on the two flagship jobs — top-k and k-way merge — on a realistic task: merging k time-sorted log streams and surfacing the slowest requests. Prove each O(…) claim with timings, not faith.
Turn the unit’s mental model into working, tested code: a correct array-backed heap with sift-up/sift-down and O(n) build-heap, a priority-queue wrapper, and two applications (top-k, k-way merge) whose measured runtimes match the O(n log k) prediction.
Implement a binary heap and priority queue from scratch (no library heap), then use them to (a) merge k time-sorted log streams into one ordered stream and (b) report the top-k slowest requests — verifying that each operation's measured cost matches its asymptotic bound.
- All correctness tests pass: the pop-everything test yields sorted output for N = 100000; top-k returns exactly the k largest with the root equal to the k-th largest; k-way merge output is globally sorted and contains every input element exactly once.
- A timing table for build-heap (n = 10^4/10^5/10^6) showing near-linear growth, placed next to the one-by-one-insert timings showing the steeper n log n curve — measured, not estimated.
- A timing table for k-way merge at fixed n with k = 2/8/32/128 showing the log k trend, next to the naive O(nk) merge times on identical input.
- A one-paragraph write-up that names, for each requirement, which heap orientation (min vs max) and which size (k vs n) you chose and why — tying each back to the eviction/advancement invariant.
- Add an indexed binary heap (track each item's current array position in a map) supporting decrease-key in O(log n), and use it to implement Dijkstra's shortest path on a small weighted graph — showing why the plain heap could not do this efficiently.
- Add a streaming top-k that processes an unbounded generator without ever materializing the full input, and demonstrate it on a stream far larger than memory using O(k) space.
- Implement in-place heap-sort (build a max-heap, then repeatedly swap-root-to-end and sift-down) and compare its wall-clock and comparison count against your language's built-in sort on the same arrays.
- Add the smallest-range variant on top of the k-way merge: while merging k arrays, track the smallest [min, max] window that contains at least one element from every array.
This is the loop a real heap problem demands: build the structure correctly (sift-up/sift-down, O(n) heapify), expose it behind the priority-queue contract, then reach for the right orientation and size for the job — a size-k MIN-heap that evicts its root for top-k, a per-stream min-heap that advances by index for k-way merge. The discipline that makes it senior-grade is verification: you measured build-heap’s linearity, the log k trend of the merge, and the heap-sort invariant, instead of trusting the big-O on the page. Do it once here and the production version is muscle memory.