Top K in a Stream
Two Heaps & K-Way Merge: lesson 3 of 4
Count once, then let a k-sized heap keep only the winners.
Lesson 3 of 4 · 6 min
Top K in a Stream
Step 1 of 13
held0/2
tally
Six events, three distinct labels. Ranking all of them is wasted work when only the top two are wanted.
The Idea
Ranking everything is wasted work when you only want k. Count first, then walk the distinct items through a min-heap capped at k.
The root is the weakest item still held. Anything that beats it takes its place; anything that does not is dropped and never looked at again.
Real-World Example
A radio station's weekly chart. Requests are tallied all week, then only five slots exist — a song enters by out-polling whichever of the five is currently lowest, and the rest never make the printed list.
The Code
import heapq
from collections import Counter
def top_k_frequent(items, k):
counts = Counter(items) # pass one: how often each appears
keep = [] # min-heap of (count, item), size k
for item, n in counts.items():
heapq.heappush(keep, (n, item))
if len(keep) > k: # over budget: evict the weakest
heapq.heappop(keep)
return [item for n, item in sorted(keep, reverse=True)]
print(top_k_frequent(["ux", "db", "ux", "api", "db", "ux"], 2)) # ['ux', 'db']
print(top_k_frequent(["a"], 3)) # ['a']Your turn
What does this print?
import heapq
keep = [(2, "db"), (3, "ux")] # the 2 best so far, weakest at the root
heapq.heappush(keep, (1, "api"))
heapq.heappop(keep)
print(keep[0])Mini quiz
1 / 3