Top-K Elements
DSA · Heaps
Theory
Top-k problems ask for the k largest, smallest or most frequent items. Sorting everything takes O(n log n), but keeping a heap of size k takes O(n log k): for the k largest, keep a min-heap of size k and replace its root whenever a bigger item arrives. Bucket sort by frequency can even solve "top k frequent" in O(n).
Why we use it
It avoids sorting the entire dataset when only a few results are needed, which matters for large streams.
When to use it
Use it for leaderboards, trending items, k closest points, top customers and streaming analytics.
How it works
- min-heap of size k
- For each element x: push x
- Heap size > k? Yes: Pop the smallest. No: Continue.
- Heap holds the k largest
Syntax
k largest with a size-k min-heap:
for x in data:
if len(heap) < k: push x
elif x > heap[0]: replace root with x
Time: O(n log k) Space: O(k)Example
def top_k_largest(nums, k):
best = [] # kept sorted, size <= k
for x in nums:
if len(best) < k:
best.append(x)
best.sort()
elif x > best[0]:
best[0] = x
best.sort()
return sorted(best, reverse=True)
def top_k_frequent(words, k):
freq = {}
for w in words:
freq[w] = freq.get(w, 0) + 1
return sorted(freq, key=lambda w: (-freq[w], w))[:k]
print("Top 3 scores:", top_k_largest([45, 92, 13, 78, 99, 61, 85], 3))
print("Top 2 topics:", top_k_frequent(["sql", "dsa", "sql", "python", "dsa", "sql"], 2))Key points
- Do not sort everything for a few results
- Size-k heap gives O(n log k)
- Min-heap for k largest, max-heap for k smallest
- Frequency problems combine a hash map and a heap