Where Heaps Shine: Top-K, Streaming Median, Merge

"The heap's killer use isn't 'sort things.' It's 'I have a flood of data and only need the boundary — the top few, the middle, the next-smallest across many streams.' Sorting all of it would be paying for order you'll never read."

Top-K: the Size-K Heap Trick

You have a billion numbers (or a stream you can't even hold in memory) and want the 100 largest. Sorting is O(n log n) and needs all n in memory. Instead, keep a min-heap of size k: push each number; whenever the heap exceeds k, pop the smallest. The heap always holds the k largest seen so far, and its root is the k-th largest — the 'cutoff.' Cost: O(n log k), and only O(k) memory. When k is much smaller than n (the top 100 of a billion), that's a massive win over a full sort, and it works on an unbounded stream where sorting isn't even possible.

Streaming Median: Two Heaps in Balance

Maintaining the median of a growing stream sounds hard — the median is the middle, and the middle moves as data arrives. The elegant trick: keep two heaps. A max-heap holds the smaller half (its top is the largest of the low values); a min-heap holds the larger half (its top is the smallest of the high values). Keep their sizes within one of each other, and the median is sitting right at the two tops. Each new value is placed and rebalanced in O(log n), and you can read the median in O(1). It's a beautiful 'meet in the middle' — two heaps facing each other across the median line.

Merge K Sorted Lists

Merging k already-sorted lists into one sorted output: put the front element of each list into a heap (k items). Pop the smallest — that's the next element of the merged output — and push the next element from that list. Repeat. The heap always holds the current frontier of k candidates, so each of the N total elements costs O(log k): an O(N log k) merge, far better than concatenating and sorting (O(N log N)). This is exactly how external sorting (data too big for memory) and log-merging work, and Python ships it as heapq.merge.

Heaps own the 'boundary' problems: top-k (size-k heap, O(n log k)), streaming median (two balanced heaps, O(log n) per item), k-way merge (heap of k fronts, O(N log k)). The common thread: you only need the edge of the order, never the whole sorted sequence.

The Thread Tying It Together

Every one of these would be wasteful with a full sort, because each needs only a boundary: the top-k cutoff, the median line, the current merge frontier. That's the heap property's promise from the first lesson, cashed out — maintain just enough order to know the extreme, and pay only for that. When you catch yourself about to sort a huge dataset to read a small ordered piece of it, stop and ask whether a heap gives you that piece for far less.

Pippa's Confession

I needed the top 20 trending items out of millions and reflexively wrote sorted(items)[:20] — sorting all millions to read twenty. Dad showed me heapq.nlargest(20, items), which keeps a size-20 heap internally: O(n log 20) instead of O(n log n), and it didn't choke. The reframe was the heap property all over again — I was buying a total order when I only needed the top edge of it. Now 'do I need ALL of this sorted, or just the boundary?' is a question I ask before every sort.

Code

Top-k, k-way merge (median sketched)·python

import heapq

# TOP-K with a size-k MIN-heap: the k largest from a stream, O(n log k), O(k) space.
def top_k(stream, k):
    heap = []                          # min-heap of the k largest seen
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:              # bigger than the current k-th largest?
            heapq.heapreplace(heap, x) # pop smallest, push x — one O(log k) op
    return sorted(heap, reverse=True)

print(top_k([7, 2, 9, 4, 1, 8, 5, 6], k=3))   # [9, 8, 7]
# Never sorted all 8; kept only the 3 best. On a billion items this is the difference
# between 'finishes' and 'runs out of memory.'

# MERGE k sorted lists with a heap (Python gives you this directly):
a, b, c = [1, 4, 7], [2, 5, 8], [3, 6, 9]
print(list(heapq.merge(a, b, c)))     # [1,2,3,4,5,6,7,8,9] — O(N log k)

# STREAMING MEDIAN sketch: a max-heap (low half) + min-heap (high half),
# kept balanced; the median sits at the two tops, O(log n) per insert.

Exercise

For the streaming median: explain why you keep the SMALLER half in a max-heap and the LARGER half in a min-heap (what does each heap's top give you?), and what 'rebalancing' means after each insert. Then: for finding the top 5 of 10 million items, give the complexity of the heap approach versus full sorting, and say when full sorting would actually be the better choice.

Hint

Max-heap top = largest of the low half; min-heap top = smallest of the high half — together they straddle the median. Rebalance = move one element across if the sizes differ by more than 1. Top-5: O(n log 5) vs O(n log n) — heap wins. But if you need the items FULLY sorted anyway, just sort once.

Top-K: the Size-K Heap Trick

Streaming Median: Two Heaps in Balance

Merge K Sorted Lists

The Thread Tying It Together

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0