AI Hints
DSA in Python · Lesson 72 of 132

Practice: Top K

The biggest few.

⏱ 2 min read▶ Video at 1:24:39🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Top K
From the video: Practice: Top K
  • 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.

top_k.pypython
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))
Output
[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.

keyvalue
Heap sizeat most k
Each stepO(log k)
TotalO(n log k)
One linerheapq.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)
Next up: Tries — a tree of letters