Heaps & Top-k
Ein Heap der Größe k findet die k größten, k nächsten oder k häufigsten in O(n log k) - ohne alles zu sortieren.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
"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.