Heap vs Sorting
Use a heap of size k when k is much smaller than n, when the data arrives as a stream, or when you cannot hold all of it in memory. Sort when you need the whole thing ordered anyway, or when n is small enough that the simpler code wins.
Top-k questions have three standard answers and the interview is usually about choosing between them. Sorting costs O(n log n) and gives you more than you asked for. A heap of size k costs O(n log k) and holds only k elements. Quickselect costs O(n) on average but needs the whole array in memory and rearranges it.
Side by side
| Dimension | Heap of size k | Sort then slice |
|---|---|---|
| Time | O(n log k) | O(n log n) |
| Extra space | O(k) | O(1) for an int[], O(n) for a copy |
| Streaming input | Works, answers after every element | Needs the whole input first |
| Gives you | The k best, unordered among themselves | Everything, fully ordered |
| k close to n | No better than sorting | Simpler, and just as fast |
| Code length | A loop with a size check | One library call |
When to pick each
Heap of size k
- k is small and n is large or unbounded: the ten largest values in a log file you cannot fit in memory.
- The answer has to be available after every element, as in a running median or a live leaderboard.
- Merging k sorted sources, where the heap holds one candidate per source and nothing more.
Sort then slice
- You need the full ordering for something else as well, such as a two-pointer pass afterwards.
- n is small, where one call to a library sort is shorter, clearer and fast enough.
- k is a large fraction of n, where log k and log n are nearly the same number.
Using a max-heap to find the k largest values. It works and it costs O(n log n), because every element goes in and you pop k times from a heap of size n. The counterintuitive answer is a min-heap of size k, whose root is the weakest of your current best and therefore the only element a newcomer has to beat. Getting that inversion the wrong way round is the most common slip on this family of questions.
Questions people ask
Why a min-heap for the k largest?
Because you want cheap access to the element you are about to throw away. The root of a min-heap of size k is the smallest of the k largest seen so far, so one comparison decides whether an arriving value belongs in the set, and one poll evicts the weakest member. A max-heap puts the wrong end at the root and gives you nothing to compare against.
When does quickselect beat both?
When you have the whole array in memory, you only need one answer, and you can tolerate rearranging the input. It averages O(n) by partitioning around a pivot and recursing into one side only. Its worst case is O(n squared) with unlucky pivots, and it cannot answer a streaming question at all, which is why heaps remain the interview default.
Is bucketing ever the right answer?
For top-k frequent elements, often. A frequency cannot exceed n, so an array of n + 1 buckets indexed by count sorts frequencies in O(n) with no comparisons. It wins when the values are bounded and loses when the keyspace is unbounded or the data streams, which is where the heap stays the safer answer.