Heaps & Top-K
A heap of size k finds the k largest, k closest, or k most frequent in O(n log k) - without sorting everything.
On this page
"Find the k largest," "the k closest," "the k most frequent" - this family of top-k problems appears constantly, and the naive answer (sort everything, take k) is often wasteful. A heap of size k solves them in O(n log k), and the trick of which heap to use is worth internalizing.
The size-k heap trick
To find the k largest elements, you might sort (O(n log n)) and take the last k. But you don't need the whole thing sorted - you only need the top k. Keep a min-heap of size k: push elements, and whenever it exceeds k, evict the smallest. What remains is the k largest, and the cost is O(n log k) - better than O(n log n) when k is small:
// k largest elements — O(n log k) with a min-heap of size k
int[] kLargest(int[] a, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap
for (int x : a) {
heap.offer(x);
if (heap.size() > k) heap.poll(); // evict the smallest → heap holds the k largest
}
return heap.stream().mapToInt(Integer::intValue).toArray();
}The counterintuitive part: to keep the largest, use a min-heap. The min-heap's root is the smallest of your current k, so it's exactly the element to drop when a bigger one arrives. (Symmetrically, for the k smallest, use a max-heap of size k.)
The pattern generalizes
The same size-k heap handles any "top k by some measure":
- k closest points to the origin - max-heap of size k keyed by distance; evict the farthest.
- k most frequent elements - build a frequency map, then a heap of size k by count.
- merge k sorted lists - a min-heap of the current head of each list; poll the smallest, push its successor - O(N log k) for N total elements.
// merge k sorted lists — min-heap of the k current heads
PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> x.val - y.val);
for (ListNode head : lists) if (head != null) heap.offer(head);
// repeatedly poll the smallest head, append it, and push its .nextWhen a heap beats sorting
If you need all elements sorted, just sort. But if you need only the top k (k ≪ n), or the data streams in and you can't hold or re-sort it all, the size-k heap is the right tool: O(n log k) time and only O(k) space, processing elements one at a time.
Min-heap for largest, max-heap for smallest
The direction trips everyone up. To retain the k LARGEST, use a MIN-heap so the smallest of your keepers is on top, ready to be evicted when something bigger arrives. To retain the k SMALLEST, use a MAX-heap. Say it out loud when you set up the PriorityQueue and you'll avoid the classic inverted-comparator bug.
A talent show has exactly k finalist chairs. As each act performs, if there's an empty chair they sit; once all k chairs are full and a better act performs, you bump the weakest current finalist to make room. You never need to rank every act against every other - you only ever compare a newcomer to the weakest finalist, who's easy to spot because they're 'on top' of your worry list. At the end, the k chairs hold the best k acts. That weakest-finalist-on-top is a min-heap, and bumping them is the O(log k) eviction.
Design a class that, as numbers arrive one at a time (a stream), can always report the k-th largest so far. Explain the structure and the cost per insertion.
To find the k LARGEST elements with a size-k heap, which heap type do you use, and why?
Key takeaways
- Top-k problems (k largest/closest/most-frequent) don't need a full sort - a size-k heap gives O(n log k).
- To keep the k LARGEST use a MIN-heap (evict the smallest keeper); for the k smallest use a MAX-heap.
- The pattern covers k-closest-points, k-most-frequent, and merge-k-sorted-lists (heap of current heads).
- For the k-th largest in a stream, a size-k min-heap exposes the answer at its root in O(1), O(log k) per insert.
- Use a heap over sorting when you need only the top k (k << n) or the data streams in.