Heap / Top-K
Keep a tiny heap of the best k; evict the weakest.
- Brute force
- O(n log n) — sort everything
- With the pattern
- O(n log k) — each push/pop is log k
- Extra space
- O(k)
In plain English
“A talent show only has k chairs on stage. Each new contestant is compared with the weakest person currently seated; if the newcomer is better, the weakest leaves and the newcomer sits. At the end, the weakest person on stage is exactly the k-th best performer overall.”
Why it's fast
Sorting everything costs O(n log n) even though you only care about k items. A size-k min-heap keeps just the current top k, with the weakest at the root for O(1) peeking and O(log k) replacement. That's O(n log k) time and O(k) memory — and it works on streams you can't sort.
Spot it when the problem says…
- kth largest / kth smallest
- top k frequent
- k closest points
- merge k sorted lists
- running median / data stream
- always process the smallest / earliest next
Visualize
Kth largest with a size-k min-heap
Find the kth largest number. Keep only the k biggest seen so far.
nums
min-heap (size ≤ 3) — root is the smallest
Keep a min-heap of at most k=3 items. Its root is "the weakest of the strongest".
1import heapq2def kth_largest(nums, k):3 heap = [] # min-heap of the k largest so far4 for x in nums:5 heapq.heappush(heap, x)6 if len(heap) > k:7 heapq.heappop(heap) # evict the smallest8 return heap[0] # smallest of the top kvariables
- k
- 3
How to apply it
- 01Pick the heap type: for k largest use a min-heap of size k (Python's
heapqis a min-heap). - 02Push each item; if the heap grows beyond k,
heappopthe smallest. - 03The root
heap[0]is the k-th largest; the heap contents are the top k. - 04For max-heap behaviour, push negated keys or
(-priority, item)tuples.
Variations you'll meet
Kth largest (size-k min-heap)
The visualizer's example.
import heapqdef find_kth_largest(nums: list[int], k: int) -> int: heap = [] for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) # evict the weakest return heap[0]Top K frequent
Count with Counter, then keep a size-k heap of (freq, value). heapq.nlargest(k, cnt, key=cnt.get) does the same.
import heapqfrom collections import Counterdef top_k_frequent(nums: list[int], k: int) -> list[int]: cnt = Counter(nums) heap = [] for val, freq in cnt.items(): heapq.heappush(heap, (freq, val)) if len(heap) > k: heapq.heappop(heap) return [val for _, val in heap]K-way merge
Seed the heap with the head of each list as (value, list_index, node); pop the smallest and push its successor.
Two heaps (median)
Max-heap for the lower half, min-heap for the upper half; rebalance so sizes differ by at most one.
Common mistakes
- Using a max-heap of all n elements for 'k largest' — that's O(n + k log n) memory you didn't need.
- Forgetting
heapqis a min-heap and not negating for max-heap behaviour. - Pushing objects that can't be compared on ties (ListNode) — add a tiebreaker index to the tuple.
- Returning
heap[-1]thinking it's the max — a heap list is not sorted.
Practice ladder
Easy → hard. Tick them off as you go.
Think you've got it?
Let the AI interviewer throw a Heap / Top-K problem at you and grade how you explain it.