Top k of a firehose
A very common ask is to keep the k largest items from a huge stream of search queries, scores, or log lines. Sorting everything costs O(n log n) and requires all n items in memory at once, which a stream may not even allow.
The heap gives a better deal, and the trick sounds backwards at first. To track the k largest items, keep a min-heap of size k.
The reason it works is what the root then means. The smallest item in that heap is the smallest of the current top k, the one on the bubble, and that is precisely the item a newcomer has to beat.
Each new value takes two steps.
- Push it onto the heap.
- If the heap now holds k+1 items, pop once, which evicts the smallest.
Whatever survives is the top k. Each item costs one push and possibly one pop on a heap that never exceeds k+1 items, so the whole pass is O(n log k) time in O(k) memory.
Those numbers are worth making concrete. For a million items with k = 10, this is a single pass doing about four steps per item while holding ten numbers, against sorting a million values.
Top k scores
Push every score, and evict whenever the heap outgrows k.
import heapq def top_k(scores, k): heap = [] for score in scores: heapq.heappush(heap, score) if len(heap) > k: heapq.heappop(heap) return sorted(heap, reverse=True) scores = [72, 95, 61, 88, 99, 45, 83, 91, 77, 68] print(top_k(scores, 3)) print(top_k(scores, 1)) print(top_k(scores, 5))
Output
[99, 95, 91] [99] [99, 95, 91, 88, 83]
The loop body is two lines, and the second one is the entire eviction policy. Pushing first and trimming after is what keeps the code free of special cases for the first k items.
The pop always removes the root, which is the smallest survivor, and that is exactly the value that no longer belongs in a top-k list once a better one arrives.
Tracing k = 1 makes it vivid. The heap holds a single value, every push briefly makes it two, and the pop discards the loser, so the survivor is the running maximum.
The final sorted(heap, reverse=True) is presentation only. Heap order does not rank the survivors among themselves, so the sort is what turns the k winners into a leaderboard, and it costs O(k log k) on a tiny collection.
Tracking the k largest uses a min-heap because the decision made on every item is whether to evict the weakest current member, and a min-heap serves the weakest in O(1).
A newcomer has exactly two possible fates. Either it beats the smallest of the current top k, in which case that member is evicted, or it does not, in which case the newcomer itself is discarded.
Both branches need instant access to the smallest member, which is the min-heap's root. A max-heap would put the strongest member on top, and the strongest member is never in question, so it would answer a question nobody asked.
Flipping the problem flips the heap. For the k smallest items you want a max-heap, so the largest of the survivors is on the bubble, and heapq fakes one by pushing negated values.
About 100 scores, and momentarily 101 between a push and its pop.
The heap is capped by construction, since any push past the limit triggers an immediate pop, so its size never drifts upward with the length of the stream.
That O(k) memory bound is the pattern's real superpower, more than the time saving. The other 999,900 scores flow through and are forgotten, which means the stream could be arbitrarily long, or even infinite, without changing the memory footprint.
Contrast the sorting approach, which needs all 1,000,000 values resident before it can answer, and cannot start until the stream ends. Streaming top-k answers correctly at every moment while holding a hundred numbers.
The structure ruined by a degraded tree height was the BST from lesson 7-3, when fed sorted input.
Sorted values sent every insert down the right side, collapsing the tree into a chain of height n and dragging search from O(log n) to O(n).
Heaps never suffer this, and the reason is structural rather than lucky. A heap is required to stay complete, filling the bottom level left to right with no gaps, so its height is always about log₂ n regardless of insertion order.
That guarantee also underwrites the array trick. Children at 2i+1 and 2i+2 only works because there are no gaps, so completeness is what buys both the height bound and the pointer-free storage at once.
The pairing is a good one to carry forward. A BST orders its nodes strictly and pays for it with a fragile shape, while a heap orders them loosely and gets a shape it can rely on.