Lesson 18.3 · Heaps and Priority Queues
Top-K: Keep a Heap of Size K
To keep the K largest items, use a min-heap of size K: the top is the weakest of the winners, and anything smaller is thrown out.
12 min
Think of it like this
A talent show that only has 3 seats on stage. A new act gets a seat only if they're better than the weakest act on stage, who then leaves. At the end, the 3 on stage are the best 3.
1.Why the opposite heap
For the K largest, the question at each new item is "is it bigger than the smallest of my current K?" That smallest is exactly what a min-heap's top gives you. Cost: O(n log k) time, O(k) space, which beats sorting when k is much smaller than n and works on streams.
For the K smallest (or K closest), flip it: a max-heap of size K.
nums = [4, 1, 7, 3, 8, 5], k = 3min-heap (size ≤ 3)(list)
Step 1/4The first three fill the heap. The top is 1, the weakest winner.
Remember
- K largest → min-heap of size K.
- K smallest → max-heap of size K.
- O(n log k), streaming-friendly.
Common mistakes
- Using a max-heap of all n items (O(n) memory and slower when k is small).