Heaps and priority queues

How does a heap answer only 'what is next', and why does it make k-way merge and top-k cheap?

Heap and priority queue

The constraint. You need the minimum, repeatedly, but you never need position seventeen. A sorted array places all n elements at a cost of n log n. A heap places only the root: it costs O(n) to build and O(log n) per extraction. It is the minimal structure that answers "what is next" and nothing else, and that restriction is the entire source of its advantage.

The k-way merge and its cost

The dominant use of a heap in data engineering is the k-way merge. Merging k sorted runs needs, at each step, the minimum among the k current run heads. A heap of size k supplies it in log k steps. Total cost: N log k comparisons for N records.

That one expression is the cost of every external sort merge pass, every LSM compaction, every multi-input merge join, and every ordered read of a partitioned topic. log k is the price of not having pre-merged. It is why compaction policy (which sets k) is a read-cost decision, not just a space decision.

import heapq
def k_way_merge(runs):                  # runs: list of sorted iterables
    heap = []
    iters = [iter(r) for r in runs]
    for i, it in enumerate(iters):
        first = next(it, None)
        if first is not None:
            heapq.heappush(heap, (first, i))
    while heap:
        value, i = heapq.heappop(heap)  # smallest head among k runs: log k
        yield value
        nxt = next(iters[i], None)
        if nxt is not None:
            heapq.heappush(heap, (nxt, i))

Use a loser tree when the merge is hot

Extracting from a binary heap and inserting the next element from the same run sifts down with two comparisons per level. A tournament tree (loser tree) stores the loser of each match at its internal node. After the winner is replaced, you walk one path from leaf to root, comparing against the stored losers: one comparison per level. That is roughly a 2× constant-factor gain on the inner loop of the most-executed algorithm in the field. Every serious external sort uses one, and almost no textbook mentions it.

Replacement selection: a historical note

The historical companion is replacement selection. Feed the tournament tree continuously during run generation, and the expected run length becomes 2M instead of M (M is memory size; the "snowplow" argument), which halves the number of runs. Be honest about this claim: it is a historical optimization that most modern systems abandoned, because it makes random I/O when building runs, and the number of merge passes is no longer the bottleneck. It is correct, it is elegant, and it is no longer how anyone builds a sorter. Know it as evidence that the binding constraint moved.

Top-N: the heap does something structurally important

A bounded heap of size k turns ORDER BY … LIMIT k into O(n log k) time and O(k) memory. That means the operator never spills, whatever the input size. That is the real prize: an unbounded-memory operator becomes a bounded-memory operator with no loss of exactness. (Compare with Probabilistic structures, where bounded memory is bought by approximation.) Here it is bought by restricting the question rather than the answer, which is strictly better when available. Whenever you see an operator with bounded state and exact output, look for a restriction on the question.

import heapq
def top_k(stream, k):
    heap = []                              # a min-heap holding the k largest seen so far
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:                  # better than the current k-th best
            heapq.heapreplace(heap, x)     # pop smallest, push x: log k
    return sorted(heap, reverse=True)      # memory never exceeded k items

When the key is time, stop comparing and start bucketing

A heap of timers costs log n per insert. A hierarchical timing wheel costs O(1) amortized: it bins time into fixed slots and advances a cursor. It works only because time advances monotonically and nothing is inserted into the past. Kafka's delayed-operation purgatory (the place where requests waiting for a condition or a timeout are held) uses a timing wheel instead of a priority queue for exactly this reason. This is a general escape: when the domain is known and roughly uniform, binning beats comparison. (You saw it in the interval-join bins above, and you will see it in range partitioning below.) Comparison is what you use when you cannot assume anything about the domain.

One hardware note

A heap is stored in an array with no pointers, which sounds cache-friendly. But the access pattern (children of node i are at 2i and 2i+1) strides across memory and misses at every level once the heap is bigger than the cache. A 4-ary heap has depth log₄ n and keeps all four children in one cache line. That is the Batch-size law again: match the fanout to the transfer unit. This is the third structure in a row where it applied.