Top-K Problems

"Top-K" problems ask for the $k$ largest, smallest, or most frequent items in a dataset. Heaps solve them cleanly in $O(n \log k)$ time and $O(k)$ space — usually better than sorting all $n$ items in $O(n \log n)$.

Top-K largest

Use a min-heap of size $k$. Scan the data; for each element, if the heap has fewer than $k$ items, push. Otherwise, if the new element is larger than the heap's minimum, pop the minimum and push the new one. At the end, the heap holds the top $k$.

Why a min-heap when we want the largest? Because we keep evicting the smallest of our current "top $k$" candidates — the min is exactly what we need cheap access to.

Top-K smallest

Mirror image: use a max-heap of size $k$. Evict the max when a smaller element appears.

Top-K frequent

Count occurrences (hash map). Then run top-K largest on the count values, with heap entries being (count, item) pairs. $O(n \log k)$ — much better than $O(n \log n)$ if $k \ll n$.

Streaming top-K

When the data is too large to fit in memory or arrives over time, the heap-of-size-$k$ pattern naturally extends: you maintain the heap as new items arrive, with $O(\log k)$ amortized cost per item.

Quickselect alternative

For static data, quickselect finds the $k$-th largest in $O(n)$ expected time (worst case $O(n^2)$). Pivot-and-partition like quicksort, but recurse only on the side containing the $k$-th rank. Faster than the heap approach when you don't care about the order of the top $k$.