All patterns
Heap / Priority Queue
Get the smallest or largest item in O(log n).
time O(n log k)space O(k)
What it is
A binary heap keeps the extreme element on top. For top-k problems a heap of size k gives O(n log k), better than sorting everything when k is small.
When to reach for it
- K largest or smallest
- Merge k sorted lists
- Running median, scheduling
- Dijkstra
Clues in the problem
- Repeatedly need the current minimum or maximum
- Sorting is overkill because only k items matter
Template
import heapqdef top_k(a, k):h = [] # min-heap of the k largestfor x in a:heapq.heappush(h, x)if len(h) > k:heapq.heappop(h)return sorted(h, reverse=True)
Practice problems
- Kth Largest Element
- Top K Frequent Elements
- Merge k Sorted Lists
- Find Median from Data Stream
Common mistakes
- Using a max-heap when a min-heap of size k is the right tool
- Python heapq is min-only; negate values for max
- Heapify is O(n), not O(n log n)