Top-K Elements Problem
You'll learn how to efficiently find the k largest or smallest elements from a collection using heaps.
The Core Challenge
Imagine you're running a leaderboard system with millions of players, but you only want to display the top 10 scores. You could sort the entire list and grab the first 10, but that wastes time sorting millions of entries you'll never use. The Top-K Elements problem asks: how can we find those k special elements without doing unnecessary work?
The Heap-Based Solution
The clever insight is to use a fixed-size heap that holds exactly k elements:
-
For k largest elements: Use a min-heap of size k. As you scan through the data, if a new element is larger than the heap's minimum (the smallest of your current top-k), evict the minimum and insert the new element. The heap always maintains the k largest items seen so far.
-
For k smallest elements: Use a max-heap of size k. If a new element is smaller than the heap's maximum, replace it. The heap maintains the k smallest items.
Why It Works
Think of the min-heap as a bouncer at an exclusive club that only holds k VIPs. The bouncer (peek operation) always knows who has the lowest status. When someone more important arrives, the least important person gets kicked out. At the end, everyone inside is guaranteed to be in the top k.
Time complexity: O(n log k) where n is the total elements—much better than O(n log n) for full sorting when k is small.
Space complexity: O(k) for the heap.
Key Takeaway: Use a fixed-size min-heap to track k largest elements or a max-heap for k smallest—maintaining the heap's inverse order creates an efficient filter that rejects non-qualifying candidates in O(log k) time per element.