Heap Patterns: Keeping Only the k Items That Matter

A heap pattern keeps only the items still in contention in a heap, a structure that gives up its smallest item first in a min-heap, or its largest first in a max-heap, in O(log k) time for a heap of k items. How it does that is the Heaps topic in Data Structures; here it is enough that push, pop and a look at the top are cheap. The cues are properties of the question: it asks for the k largest, smallest or closest items; for the next smallest among several sorted sources; or for the middle of values that keep arriving. In each, only a few values can be in the answer, and the heap holds only those.

For the k largest, the heap is a min-heap of size k, and it keeps one invariant: it holds the k largest items seen so far, and its top is the smallest of them. That top is the item to throw away next, so each new item is compared with the top alone. If it is larger, it replaces the top; otherwise it cannot be among the k largest and is skipped. The values 7 2 9 4 11 5 8 with k = 3 show it.

Only the top is in a known place; 11 sits before 9 in the array because a heap orders each parent before its children and nothing more. Each item costs at most one O(log k) replacement, so the pass is O(n log k) time for n items and O(k) extra space, and it works on a stream, since it never needs the items it has passed.

A talent show that keeps only three finalists works the same way: each new act is compared with the weakest finalist and replaces them only if better. The likeness breaks at the judges, who can rank all three finalists at once, while the heap knows only which one is weakest; reading the k items in order means sorting them at the end.