Using PriorityQueue for Top-K Problems
You'll learn how to efficiently find the K largest or smallest elements in a dataset using PriorityQueue.
The Classic Top-K Problem
Imagine you're scanning through thousands of test scores and need to find the top 10 highest scores. You could sort everything and grab the top 10, but that's overkill—like organizing your entire closet just to find your favorite shirt. A PriorityQueue lets you track just the K items you care about.
The Strategy
For K largest elements: Use a min-heap (natural ordering or min-comparator) of size K. As you scan elements:
- Add to the queue if it has fewer than K elements
- If full and the new element is larger than the smallest (the head), remove the head and add the new element
- The queue always contains your K largest seen so far
For K smallest elements: Use a max-heap (reverse comparator) of size K. Follow the same logic but keep the K smallest.
Why It Works
The heap's head is always your "gatekeeper"—the threshold element. By maintaining only K elements and evicting the worst one when you find something better, you avoid storing everything. This gives you O(N log K) time complexity instead of O(N log N) for full sorting, and you only use O(K) space instead of O(N).
The Analogy
Think of a talent show with 5 judge seats. As contestants perform, judges stay seated unless someone better comes along—then the lowest-scoring judge gets replaced. At the end, the 5 seated judges are your top performers.
Key Takeaway: Use a size-limited PriorityQueue as a moving filter—a min-heap for top-K largest or max-heap for top-K smallest—to efficiently track extremes without sorting entire datasets.