You rarely need a full sort
When a problem asks for the k largest, k smallest, or k most frequent items, sorting everything is overkill. You only care about a handful of winners, so the top k elements pattern maintains a heap that holds exactly k candidates as you stream through the data.
The bounded heap trick
To find the k largest, keep a min heap of size k.
- Push each new element onto the heap.
- If the heap grows beyond k, pop the smallest, which is the heap top.
- After processing everything, the heap holds the k largest, and its top is the kth largest.
The heap stays small, so each insert and removal touches only a shallow tree rather than the whole dataset.
Why a min heap for largest
It feels backward, but a min heap lets you cheaply evict the weakest surviving candidate. The smallest of your current winners sits right at the top, ready to be discarded the instant something better arrives. Frequency problems work the same way once you first count occurrences.
Key idea
Maintain a heap of size k so the weakest current winner sits at the top, letting you keep only the best candidates without sorting the whole input.