Heaps & Priority Queues
Always grab the smallest (or largest) item in O(log n) — top-K, scheduling, and merging problems
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
A is a tree-shaped structure that answers one question fast, repeatedly: "what's the smallest (or largest) item I currently have?" Python's heapq is a min-heap — the smallest item is always at index 0.
import heapq
nums = [5, 1, 8, 2, 9]
heapq.heapify(nums) # O(n) — rearrange in place into heap order
print(nums[0]) # 1 — smallest is always at the root
heapq.heappush(nums, 0) # O(log n) — insert, re-balance
smallest = heapq.heappop(nums) # O(log n) — remove and return the smallestWhy not just sort? Sorting the whole collection is O(n log n) up front. A heap lets you insert and extract-min one at a time at O(log n) *each* — which wins whenever items arrive over time, or you only ever need the current min/max, not a full ordering.
Top-K pattern — finding the K largest items without sorting everything:
python def top_k_largest(nums, k): heap = [] # min-heap of size k for n in nums: heapq.heappush(heap, n) if len(heap) > k: heapq.heappop(heap) # evict the smallest — keeps only the k largest return heap # the k largest, heap[0] is the smallest of them print(top_k_largest([5, 1, 8, 2, 9, 3], k=3)) # [5, 8, 9] in some order
The trick: to find the K *largest*, keep a min-heap capped at size K — the smallest item in that small heap is always the weakest of the current top-K, so it's the one to evict when a bigger item shows up.
Python has no max-heap built in — simulate one by negating values: ``python max_heap = [] for n in nums: heapq.heappush(max_heap, -n) # store negated largest = -heapq.heappop(max_heap) # negate back on the way out
When to reach for a heap: "K largest/smallest," "kth largest element," merging K sorted lists, scheduling by priority, running median, Dijkstra's shortest path — anywhere you repeatedly need "the current min/max" from a changing collection.
Examples
Kth largest element in a stream
A capped min-heap is a sliding 'top-K' window over a stream
import heapq
class KthLargest:
def __init__(self, k):
self.k = k
self.heap = [] # min-heap, capped at size k
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # discard anything that's not top-k
return self.heap[0] # kth largest = smallest of the top-k
stream = KthLargest(k=3)
for n in [4, 5, 8, 2]:
print(stream.add(n)) # 4, 4, 4, 5 -- running 3rd-largestMerging K sorted lists
The heap always holds exactly one "next candidate" per list — extract-min picks the global next value in O(log k)
import heapq
def merge_k_sorted(lists):
heap = []
# seed the heap with the first element of each list
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0)) # (value, list_index, elem_index)
result = []
while heap:
val, i, j = heapq.heappop(heap)
result.append(val)
if j + 1 < len(lists[i]):
heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
return result
print(merge_k_sorted([[1, 4, 7], [2, 5], [3, 6, 9]])) # [1,2,3,4,5,6,7,9]How well did you understand this?
Practice Problems
Next in Algorithms & Data Structures
Dynamic Programming