Top k of a firehose
A very common ask: from a huge stream (search queries, scores, log lines), keep the k largest. Sorting everything costs O(n log n) and needs all n items in memory at once. The heap gives a better deal.
The trick sounds backwards at first: to track the k LARGEST items, keep a min-heap of size k. Its root is then the smallest of your current top k, the item "on the bubble".
For each new value:
- push it onto the heap
- if the heap now holds k+1 items, pop once, evicting the smallest
Whatever survives is the top k. Each item costs one push and maybe one pop on a heap that never exceeds k+1 items: O(n log k) time, O(k) memory. For a million items with k = 10, that is a ~1M × 4-step pass holding 10 numbers, versus sorting a million.
Code exercise · python
Your turn: implement `top_k(scores, k)` with the size-k min-heap: push each score, pop whenever the heap grows past k, and finally `return sorted(heap, reverse=True)` to present the winners in descending order.
Quiz
Why does tracking the k LARGEST items use a MIN-heap?
Problem
You keep the top 100 scores from a stream of 1,000,000 with the size-k min-heap pattern. Roughly how many scores are held in memory at any moment?
Quiz
Course callback: a heap pop is O(log n) because repairs walk one root-to-leaf path. Which earlier structure had its efficiency destroyed when that same tree height degraded from log n to n?