Heaps and Priority Queues
Always get the smallest (or largest) item fast. Learn how a binary heap lives inside a plain array, how sift-up and sift-down keep the heap property, why building a heap is linear, and how to use heapq for top-k, merging and scheduling problems.
The line where urgent things go first
An emergency room does not treat patients in arrival order. A nurse triages: whoever is most urgent goes next, whenever they arrived. An operating system does the same with processes, a game does it with events scheduled by time, and Dijkstra's shortest path algorithm does it with vertices ordered by distance. The common need is a collection that supports two operations quickly: add anything, and remove the most important item. That is a priority queue.
The obvious implementations disappoint. An unsorted list adds in constant time but must scan everything to find the minimum. A sorted list finds the minimum instantly but must shift elements to insert. Each makes one operation cheap and the other linear. A binary heap is the compromise that makes both logarithmic, and it does so with no pointers and almost no overhead.
A complete binary tree in which every parent is less than or equal to its children. The smallest element is always at the root. A max-heap reverses the rule. A heap is only partially ordered: siblings and cousins have no defined relationship.
A tree stored in an array
A heap is drawn as a tree but stored as a flat array. The trick is that the tree is complete: every level is full except possibly the last, which fills from the left. That regular shape means there are no gaps, and positions can be computed with arithmetic instead of pointers. With a zero-based array, the children of the element at index i sit at 2i + 1 and 2i + 2, and its parent sits at (i - 1) // 2.
The heap property is much weaker than sortedness. It says only that each parent is no larger than its children. The array [1, 3, 2, 7, 4, 5] is a valid heap even though it is not in order, and that looseness is exactly what makes maintaining a heap cheap. You pay for just enough order to find the minimum.
tree: 1
/ \
3 2
/ \ /
7 4 5
array: index 0 1 2 3 4 5
value [1, 3, 2, 7, 4, 5]
children of index 1 (value 3): indexes 3 and 4 (values 7, 4)
parent of index 5 (value 5): index 2 (value 2)Push and pop: sift up, sift down
Push. Append the new item at the end of the array (the next free spot in the last level, so the tree stays complete). It may be smaller than its parent, breaking the property, so sift up: while it is smaller than its parent, swap them. In the worst case it climbs to the root, which is the height of the tree, about log2 n levels. Cost: O(log n).
Pop the minimum. The minimum is at index 0. Removing it leaves a hole at the root. Fill the hole with the last element of the array (which keeps the tree complete) and then sift down: while the item is larger than one of its children, swap it with the smaller child. Choosing the smaller child matters, because it becomes the new parent of the other child and must not be larger than it. Cost: O(log n).
Peeking at the minimum is O(1) because it is always sitting at index 0.
1class MinHeap:2 def __init__(self):3 self.a = []45 def push(self, x):6 a = self.a7 a.append(x)8 i = len(a) - 19 while i > 0 and a[i] < a[(i - 1) // 2]: # sift up10 parent = (i - 1) // 211 a[i], a[parent] = a[parent], a[i]12 i = parent1314 def pop(self):15 a = self.a16 top = a[0]17 last = a.pop()18 if a:19 a[0] = last20 i = 021 while True: # sift down22 left, right, smallest = 2 * i + 1, 2 * i + 2, i23 if left < len(a) and a[left] < a[smallest]:24 smallest = left25 if right < len(a) and a[right] < a[smallest]:26 smallest = right27 if smallest == i:28 break29 a[i], a[smallest] = a[smallest], a[i]30 i = smallest31 return top3233heap = MinHeap()34for value in [5, 3, 8, 1, 9, 2, 7]:35 heap.push(value)36 print("push", value, "->", heap.a)3738out = []39while heap.a:40 out.append(heap.pop())41print("popped in order:", out)
push 5 -> [5] push 3 -> [3, 5] push 8 -> [3, 5, 8] push 1 -> [1, 3, 8, 5] push 9 -> [1, 3, 8, 5, 9] push 2 -> [1, 3, 2, 5, 9, 8] push 7 -> [1, 3, 2, 5, 9, 8, 7] popped in order: [1, 2, 3, 5, 7, 8, 9]
Building a heap in linear time
Given n items, you could push them one by one for O(n log n). There is a faster way. Treat the array as a heap-shaped tree that is merely not yet valid, and fix it from the bottom: starting at the last parent and moving back to the root, sift each node down. This is heapify.
Why is it O(n) when each sift-down can cost log n? Because most nodes are near the bottom, where sifting is short. Half of the nodes are leaves and need no work at all; a quarter can move down at most one level; an eighth, two levels; and so on. Add it up and the geometric series converges to a constant multiple of n. It is a lovely example of an analysis where the crude bound (n times log n) is correct but not tight.
Heap sort follows: heapify, then pop the minimum n times. That is O(n log n) in the worst case with O(1) extra memory when done in place, though in practice it is usually slower than quick sort because of its poor cache behaviour.
Using heapq in real code
Python's heapq module is a min-heap over an ordinary list: heappush, heappop, heapify, and heap[0] for a peek. There is no max-heap, so store negated numbers, or push tuples whose first element is the negated priority. Tuples compare element by element, so (priority, tiebreaker, item) keeps the heap from ever comparing two items that cannot be compared.
Three patterns cover most uses. Top-k: keep a heap of size k and replace the root when a better item arrives, giving O(n log k), which beats sorting everything when k is small. Merge sorted streams: keep one entry per stream in the heap and always pop the smallest. Scheduling: pop the next task by priority or deadline.
heapq works on a plain list, so mutating the list yourself (for example heap.sort(), or heap[2] = 0) breaks the heap property silently. Only use heappush, heappop, heapreplace and heapify to change it.
1import heapq23# 1. The k largest values with a heap of size k: O(n log k)4def top_k(values, k):5 heap = []6 for v in values:7 if len(heap) < k:8 heapq.heappush(heap, v)9 elif v > heap[0]:10 heapq.heapreplace(heap, v) # pop smallest, push v, in one step11 return sorted(heap, reverse=True)1213data = [41, 7, 99, 23, 56, 3, 88, 15, 72]14print("top 3:", top_k(data, 3))15print("matches library:", top_k(data, 3) == heapq.nlargest(3, data))1617# 2. Merge three sorted lists18streams = [[1, 4, 9], [2, 3, 10], [5, 6, 7, 8]]19print("merged:", list(heapq.merge(*streams)))2021# 3. Max-priority tasks: negate the priority, add a counter for ties22tasks = [("write report", 2), ("fix outage", 9), ("reply to mail", 1), ("review pr", 5)]23heap = []24for order, (name, priority) in enumerate(tasks):25 heapq.heappush(heap, (-priority, order, name))26while heap:27 neg, _, name = heapq.heappop(heap)28 print("do next:", name, "(priority", -neg, ")")
top 3: [99, 88, 72] matches library: True merged: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] do next: fix outage (priority 9 ) do next: review pr (priority 5 ) do next: write report (priority 2 ) do next: reply to mail (priority 1 )
Costs and what a heap cannot do
A heap is built for the extreme element. It does not support fast arbitrary search, because apart from the root and the parent-child rule there is no order to exploit; finding an arbitrary value is O(n). It does not iterate in sorted order. And it does not support cheap deletion of an arbitrary item or a change of priority without extra bookkeeping, which is why the lazy "skip stale entries" trick in Dijkstra exists.
Priority queue implementations
| Structure | Push | Pop min | Peek min | Build from n items |
|---|---|---|---|---|
| Unsorted list | O(1) | O(n) | O(n) | O(n) |
| Sorted list | O(n) | O(1) at the front | O(1) | O(n log n) |
| Binary heap | O(log n) | O(log n) | O(1) | O(n) |
Check your understanding
These questions probe the structure and its invariants.
In a zero-based array heap, which indexes hold the children of the element at index 4?
Quick Syntax & Reference Sheet
| Concept / Rule | Syntax / Usage |
|---|---|
| Index arithmetic | parent = (i - 1) // 2; left = 2*i + 1; right = 2*i + 2 |
| heapq basics | heapq.heappush(h, x); heapq.heappop(h); h[0]; heapq.heapify(lst) |
| Max-heap trick | heappush(h, -x); largest = -heappop(h) |
| Top-k | heapq.nlargest(k, data) # or keep a size-k min-heap |
Common Pitfalls & Developer Mistakes
Expecting heapq to give a max-heap
Why it happens: heapq is min-only.
Treating the heap list as sorted
Why it happens: Only the root is guaranteed to be the minimum; the rest of the list is just heap-ordered.
Pushing items that cannot be compared when priorities tie
Why it happens: Python then compares the next tuple element, which may raise TypeError.