Top K Elements Pattern

Why Bounded Heaps Work

Top-K questions usually do not require a complete ranking. They only care about a tiny frontier: the best k items seen so far. A bounded heap is ideal because it keeps exactly that frontier and forgets everything that can no longer matter. If you want the k largest values, keep a min-heap of size k. The smallest element inside that heap is the weakest winner, so any future value that fails to beat it can be ignored instantly.

That “weakest winner” idea is the conceptual core. The heap is not storing the final answer because heaps are pretty; it is storing the admission threshold. The root tells you how hard it is for a new candidate to enter the winning set. This is why the pattern shines when k is much smaller than n: you never spend full sorting work on data that never came close to the border.

The pattern is flexible about what “best” means. It can be largest value, highest frequency, smallest distance, or any custom score. Once you define an ordering, the rest is mechanical: keep the k winners and eject the weakest whenever a better candidate arrives.

Worked Example

Suppose you want the 3 largest values from [9, 4, 1, 7, 12, 3, 8]. Start with an empty min-heap. Insert 9, 4, and 1; the heap now contains the three current winners {1,4,9} and the root 1 is the weakest winner. Next comes 7. Since 7 > 1, it deserves a spot, so remove 1 and insert 7. The heap becomes {4,7,9}.

Then 12 arrives and beats the weakest winner 4, so replace 4. The winners become {7,9,12}. Next is 3, which does not beat 7, so discard it instantly. Finally 8 arrives, beats 7, and replaces it. The final heap contains {8,9,12}. The algorithm never cares about the full internal order among losers.

Implementation

If the problem asks for a single kth element rather than the full set, the heap root is already the answer at the end. If it asks for all winners in sorted order, you may sort the final heap contents, but that is only k log k, not n log n.

Choosing the Right Heap

A good self-check is: “Which current winner would I kick out first if a better candidate appears?” Build the heap so the answer to that question sits at the root. That sentence prevents the most common mistake, which is exposing the wrong end of the winner set.

Practice Problems

Quiz