Heaps & Priority Queues
Need to repeatedly find the smallest (or largest) element? A heap gives you that in O(log n). It's like a VIP queue where the most important person is always at the front.
The Core Idea
A heap is a tree where every parent is smaller (min-heap) or larger (max-heap) than its children. The root is always the min or max. When you add or remove, the heap reshuffles to maintain this property.
The Key Insight
Use a heap when you need to repeatedly extract the min/max, or when you need the "top K" of something.
Python's heapq Module
Python only has min-heap. For max-heap, negate the values:
import heapq
# Min heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap)) # 1 (smallest)
# Max heap (negate values)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
print(-heapq.heappop(max_heap)) # 3 (largest)Classic: Top K Frequent Elements
def topKFrequent(nums, k):
count = Counter(nums)
# Min heap of size k
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for freq, num in heap]| Operation | Time |
|---|---|
| Push | O(log n) |
| Pop (min/max) | O(log n) |
| Peek (min/max) | O(1) |
| Heapify array | O(n) |
When to Use a Heap
- Top K elements - K largest, K most frequent
- Merge K sorted lists - Always pick the smallest head
- Running median - Two heaps (min + max)
- Dijkstra's algorithm - Pick minimum distance node
- Task scheduling - Process by priority
Pro Tip
For Top K problems, a heap of size K is often more efficient than sorting everything. You keep only what you need.