Top-K Elements (Heap / QuickSelect)

When someone asks for the top five best-sellers out of a million products, the tempting move is to sort all million and read off the last five. It works, and it wastes almost all of its effort: you carefully ordered 999,995 items you were never going to look at. The Top-K pattern is the refusal to do that. You only ever need to remember the best few candidates seen so far, so that is all you keep.

The trick that makes "keep the best k" efficient is a heap, and specifically a counterintuitive one: to track the k largest values, you hold them in a min-heap of size k. The reason is that the one element most in danger of being kicked out is the smallest of your current top k, and a min-heap keeps exactly that element sitting at the root where you can compare and evict it in O(log k).

A heap of size k: keep the winners, drop the rest

Walk the data once. Fill the heap until it holds k elements, then for everything after, compare against the root: if the newcomer beats the weakest survivor, swap it in.

import heapq

def top_k(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:                 # better than the weakest of the current top k
            heapq.heapreplace(heap, x)    # pop the smallest, push x, in one step
    return heap

Each element costs at most O(log k), so the whole scan is O(n log k), and crucially the memory is O(k), not O(n). For k far smaller than n, which is the usual case, that is a night-and-day difference from sorting, and it never needs the whole dataset in hand at once.

A min-heap of size three holding the current top values 7, 8 and 9, with the smallest, 7, at the root; a newcomer like 10 only has to beat the root to earn a place, evicting 7 in log k time while the rest of the data is never sorted.

In the wild: trending items from a stream

That last point, never needing the whole dataset at once, is why this pattern owns real-time analytics. Picture a trending dashboard: a firehose of search queries or played tracks, and you want the current top ten. You cannot sort a stream that never ends. So you keep a running count of how often you have seen each item, and a min-heap of size ten keyed by that count, holding only the current leaders.

import heapq
from collections import Counter

def top_k_frequent(stream, k):
    counts = Counter(stream)                       # item -> how many times seen
    heap = []
    for item, freq in counts.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, item))
        elif freq > heap[0][0]:                    # more frequent than the weakest leader
            heapq.heapreplace(heap, (freq, item))
    return [item for _, item in heap]

It is the same pattern as the best-sellers, with one twist: the value you rank by is a frequency you tallied first, so a hashmap feeds the heap. And it is genuinely the same class of problem, because the heap does not care whether it is ranking sales, scores, or counts; it only ever holds the k best candidates and cheaply retires the weakest. Swap the fixed count for a rolling window and you have live trending, the backbone of "what is hot right now" on every large platform.

The trigger

The problem asks for the k largest, smallest, most frequent, closest, or highest-scoring, and k is much smaller than n. The tell is "top k" or "k nearest" without any need to order the rest. If you catch yourself about to sort everything to grab a handful, that is the pattern knocking.

Where it shows up

  • Leaderboards and best-of lists: top sellers, high scores, most-viewed.
  • Frequency ranking: k most common words, trending queries, hot keys, always a hashmap feeding a heap.
  • Geometric and streaming variants: k closest points to a target, k largest in an unbounded stream.

Where it bites

The direction of the heap is the classic confusion: largest-k wants a min-heap, smallest-k wants a max-heap (in Python, negate the values). Get it inverted and you evict the wrong end and quietly return garbage. Also mind the ties and the return contract: a heap gives you the k best but not in sorted order, so if the caller expects them ranked, you still owe a final O(k log k) sort of just those k.

When it is the wrong tool

If you actually need everything in order, skip the heap and just sort; Top-K only wins when you are throwing most of the data away. When k approaches n, the heap's O(n log k) collapses back toward a full sort with more overhead, so sort instead. And if you need the k-th element exactly once on a static array, a heap is not the sharpest tool: QuickSelect partitions the array to find it in O(n) average time, which the next pattern covers. QuickSelect's catch is that it mutates the array and needs random access, so for streams or linked data the heap is still the right home.

Its neighbors

It is the practical face of Kth Largest/Smallest Elements, where QuickSelect takes center stage for the one-shot case. It leans on Hashmaps and Frequency Counting whenever "top" means "most frequent," and on solid Heap fundamentals underneath. For the k best within a moving range, it joins forces with Sliding Window.

References