# 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). ```python 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 `heapq` is 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](https://www.linkjob.ai/). This guide is general study material.*