Find the top k with heaps
Use a priority queue to get the smallest or largest items quickly.
- Explain what a heap guarantees.
- Solve top-k problems in O(n log k).
- Use Python’s heapq module.
A heap (priority queue) keeps its smallest item instantly available at the top. Adding an item and removing the top each take O(log n). Heaps shine whenever you repeatedly need “the next smallest” or “the k largest” without fully sorting: top-k elements, merging k sorted lists, scheduling, and Dijkstra’s shortest path.
Heaps in Python
heapqimplements a min-heap on a plain list:heappush(h, x),heappop(h), andh[0]to peek.- For a max-heap, push negated values or use
(-priority, item)tuples. heapq.nlargest(k, items)andheapq.nsmallest(k, items)solve top-k directly.- Top-k trick: keep a min-heap of size k. For each new item, push it; if the heap grows past k, pop the smallest. The heap ends holding the k largest, in O(n log k) time.
1import heapq
2
3def k_largest(nums, k):
4 heap = []
5 for num in nums:
6 heapq.heappush(heap, num)
7 if len(heap) > k:
8 heapq.heappop(heap) # drop the smallest
9 return sorted(heap, reverse=True)
10
11print(k_largest([3, 1, 5, 12, 2, 11], 3))[12, 11, 5]
Why a min-heap for the largest items? The heap’s top is the smallest of the current top k - the one to evict when something bigger arrives. Sorting everything would be O(n log n); the size-k heap is O(n log k), which matters when k is much smaller than n.
Key takeaways
Heaps give O(log n) push/pop and O(1) peek at the minimum.
Keep a size-k min-heap to find the k largest in O(n log k).
Negate values for a max-heap in Python.
Lesson quiz
5 questions · pass with 4 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: solve interview problems
Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.
Find the k most frequent words
Read k, then a line of words. Print the k most frequent words, one per line, from most to least frequent. Break ties alphabetically.
- Top two
- Alphabetical tie-break
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…