Practice: Top K
The biggest few.
You have a million scores, and you want the top three. Sorting everything is O of N log N. With a heap, you can do better, by only ever keeping the best few. Pause and think how.

- A million scores
- Just the top three
- Keep only the best few
A small heap of size k
We keep a min heap of at most K items. Its top is the smallest of our current best. Each new score is pushed in, and if the heap grows past K, we pop the smallest. At the end, the heap holds the K biggest. Run it. Heap Q also has n largest, which does the same thing in one line.
import heapq, random
def top_k(scores, k):
heap = []
for s in scores:
heapq.heappush(heap, s)
if len(heap) > k:
heapq.heappop(heap)
return sorted(heap, reverse=True)
random.seed(7)
scores = [random.randint(0, 1_000_000) for _ in range(1_000_000)]
print(top_k(scores, 3))
print(heapq.nlargest(3, scores))[999999, 999998, 999997] [999999, 999998, 999997]
Why it is fast
Each push or pop works on a heap of only K items, so it costs O of log K. Over N scores, the total is O of N log K. When K is three and N is a million, that's much faster than sorting everything. It also uses only O of K memory.
| key | value |
|---|---|
| Heap size | at most k |
| Each step | O(log k) |
| Total | O(n log k) |
| One liner | heapq.nlargest(k, xs) |
Summary
To find the top K, keep a min heap of size K, and pop the smallest when it overflows. It's O of N log K. Next, a tree made for words. The trie.
Key takeaways- Min heap of size k
- Pop when too big
- O(n log k)