Keep a min-heap of size k. Its root is always the weakest of your current top-k — exactly the one to evict.
“K largest / K most frequent” → min-heap capped at k (max-heap for k smallest)
Pattern: Top-K Largest in One Pass
The stream never stops; the heap of champions stays at size 3. Press ▶.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Top K Smallest — Max-Heap of Size k
Flip the comparison: use a MAX-heap of size k. The root is the largest of the k smallest — the weakest member of the bottom-k. When something smaller arrives, evict the root.
Same stream [5,2,10,9,3,8], k=3. We maintain a max-heap of size 3. Once full, each new element smaller than the root evicts it. The root is always the biggest of the k smallest — exactly the kth smallest overall.
1
heap = max-heap, max size k
2
for x in stream:
3
if size < k:
4
push(x) # still filling
5
elif x < root:
6
replace root with x # evict biggest of bottom-k
7
# root now = k-th smallest overall
public int[] topK(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(); // min
for (int x : nums) {
if (heap.size() < k) {
heap.offer(x);
} else if (x > heap.peek()) {
heap.poll();
heap.offer(x);
}
}
int[] res = new int[k];
for (int i = k - 1; i >= 0; i--) res[i] = heap.poll();
return res;
}import heapq
def top_k(nums, k):
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x)
return sorted(heap, reverse=True)vector<int> topK(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> heap; // min
for (int x : nums) {
if ((int)heap.size() < k) heap.push(x);
else if (x > heap.top()) { heap.pop(); heap.push(x); }
}
vector<int> res;
while (!heap.empty()) { res.push_back(heap.top()); heap.pop(); }
reverse(res.begin(), res.end());
return res;
}// with the MinHeap class from before
function topK(nums, k) {
const heap = new MinHeap();
for (const x of nums) {
if (heap.size() < k) heap.push(x);
else if (x > heap.peek()) {
heap.pop();
heap.push(x);
}
}
const res = [];
while (heap.size()) res.unshift(heap.pop());
return res;
}For most frequent, count first (HashMap), then push (count, value) pairs — same size-k heap.
Min-heap of size k = a club that only lets in elements better than its weakest member.
Common Mistakes
- Using a max-heap of everything then popping k times: O(n log n) and O(n) memory instead of O(n log k)/O(k).
- Forgetting the
x > rootcheck — pushing every element destroys the size guarantee. - Returning the heap as-is: it’s unordered; sort before returning “top-k”.
Complexity
| Approach | Time | Space |
|---|---|---|
| Sort everything | O(n log n) | O(1)–O(n) |
| Max-heap all items | O(n + k log n) | O(n) |
| Min-heap size k | O(n log k) | O(k) |
Premium Content
Unlock Top K Problems and all premium lessons with a subscription.
From ₹199.99/year — See plans