Top-K Problems with Heaps: When and How to Use Them
"Find the k most frequent elements", "k closest points to the origin", "kth largest element in a stream": whenever a question says top k, consider a heap.
Rule of thumb
To keep the k largest items, use a min-heap of size k. The smallest of your current top k sits at the root, so each new item is compared with it in O(log k).
import heapq
from collections import Counter
def top_k_frequent(nums, k): # LeetCode 347
heap = []
for val, cnt in Counter(nums).items():
heapq.heappush(heap, (cnt, val))
if len(heap) > k:
heapq.heappop(heap)
return [v for _, v in heap]
Total time is O(n log k), better than sorting (O(n log n)) when k is small.
Alternatives to mention
- Bucket sort by frequency: O(n) for Top K Frequent because frequencies are bounded by n.
- Quickselect: average O(n) for kth largest, but O(n²) worst case; say so.
heapq.nlargest(k, iterable)is fine in Python, but be ready to implement it yourself.
Streaming version (LeetCode 703)
Keep the size-k min-heap as state; each add pushes, pops if the size exceeds k, and returns heap[0].
Pitfalls
- Python's
heapqis a min-heap only; negate values for a max-heap. - Tuples compare element by element, so ties can fall through to comparing objects that don't support it. Add an index as a tie-breaker.
Disclosure: I help build an AI interview copilot at Linkjob. This guide is general study material.