# Heaps for Top-k — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/x-heap

> Keep only what matters.

## heapq and the size-k heap

Python's `heapq` is a **min-heap** with O(log n) push and pop. For the k largest items, keep a min-heap of size k and pop whenever it grows past k: the root is then the k-th largest, in O(n log k) time and O(k) space. `heapq.nsmallest` and `nlargest` with a key handle top-k with ties (such as frequency then alphabetical order). Heaps also merge k sorted lists and schedule tasks.

## Best-first and sort-first

Heaps keep the best few items, sorting tames intervals, and greedy choices work when local best is globally best.

![Three ideas: heaps, intervals, greedy.](assets/figures/dsa-interview-patterns/section-7-map.svg) — Figure 7.1 — Heaps, intervals and greedy choices.

## Top-k frequent words and the k-th largest, run

I ran this with Python 3.12.3 (standard library only). "the" appears 4 times and "is" 3 times, then "sunny"; the 2nd largest of the first list is 5 and the 4th largest of the second is 4.

```python
# Heaps: top-k frequent words and the k-th largest number
import heapq
from collections import Counter

def top_k_frequent(words, k):
    counts = Counter(words)
    return heapq.nsmallest(k, counts, key=lambda w: (-counts[w], w))

def kth_largest(nums, k):
    heap = []                             # min-heap of the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

words = "the day is sunny the the the sunny is is".split()
print(top_k_frequent(words, 3))
print(kth_largest([3, 2, 1, 5, 6, 4], 2), kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))
```

Output:

```
['the', 'is', 'sunny']
5 4
```

## Negate for a max-heap

heapq has no max-heap; push negative values or tuples with negated keys.

**Quiz:** What does a min-heap of size k contain after scanning an array for the k largest?

- [ ] The k smallest elements
- [x] The k largest elements, with the k-th largest at the root
- [ ] All elements sorted
- [ ] Only the maximum

*Answer:* The k largest elements, with the k-th largest at the root. Pop the smallest when over k.