What comes next?
In the emergency department of a hospital in Manila, patients are not seen in order of arrival. A nurse assigns each a priority, and whenever a doctor becomes free, the most urgent patient waiting goes next. New patients arrive all the time, so the order is never finished: the department needs, again and again, the most urgent of whoever is waiting right now.
Computers face the same question constantly. An operating system picks the next process to run. Python's asyncio event loop keeps its timers ordered by deadline and wakes the earliest. A video site wants the ten most-watched clips of the day out of millions. A log system merges sorted files from fifty servers into one sorted stream. Dijkstra's shortest-path algorithm repeatedly needs the nearest unfinished vertex (see Shortest paths).
The abstract data type for all of these is the priority queue: insert items with priorities, and repeatedly remove the one with the smallest (or largest) priority. The structures from earlier lessons do it badly. An unsorted list inserts in but must scan everything to find the minimum, . A sorted list finds the minimum instantly but inserts in . A balanced search tree manages for both, but carries pointers, colours and rotations for an ordering we mostly don't need. The binary heap does both in , peeks at the minimum in , can be built from items in , and lives in a plain array with no pointers at all.
Definitions
Definition— priority queue
A priority queue stores items with comparable priorities and supports push(x), peek() (return a minimum item) and pop() (remove and return a minimum item). This is a min-priority queue; a max-priority queue is the mirror image. Some applications also need decrease_key, which lowers the priority of an item already inside.
Definition— complete binary tree
A binary tree is complete if every level is full except possibly the last, which is filled from the left.
Definition— binary heap
A binary min-heap is a complete binary tree in which every node's key is less than or equal to the keys of its children (the heap property). It follows that the root holds a minimum, and that every root-to-leaf path is sorted in non-decreasing order. Nothing is promised about the order between siblings or cousins.
Definition— array layout
Store the nodes of a complete binary tree level by level, left to right, in an array a[0..n-1]. Then the root is a[0], the children of a[i] are a[2*i + 1] and a[2*i + 2], and the parent of a[i] is a[(i - 1) // 2]. Completeness is exactly what makes this numbering leave no gaps.
Push and pop: sifting up and down
Both operations follow the same pattern: first keep the tree complete (the shape is easy to fix in an array: add or remove at the end), then repair the heap property, which can now be broken in exactly one place.
Push. Append the new item at the end of the array, which is the next free spot on the bottom level. It may be smaller than its parent. Sift up: while the item is smaller than its parent, swap them.
Pop. The minimum is at the root. Save it, move the last item of the array to the root, and shrink the array by one. The new root may be larger than its children. Sift down: while the item is larger than its smaller child, swap it with that smaller child. (Swapping with the smaller child matters: that child becomes the parent of the other, so it had better be the smaller of the two.)
Theorem— Heap operations
push and pop preserve the heap property, and each takes time on a heap of items. peek takes .
Proof
Sift up. Invariant: the heap property holds for every parent–child pair except possibly the pair formed by the moving item and its current parent . Initially the only new pair is with its parent, so the invariant holds. If , swap them. Now 's pair with its new children is fine: one child is , and the other was a child of before, so it is . And , moved down, sits above nodes that were all in its subtree before, which were all . So the only possibly broken pair is again with its new parent, one level up. The loop stops when reaches the root or its parent is , and then nothing is broken.
Sift down is symmetric: the only possibly broken pairs are between the moving item and its children. Swapping with its smaller child puts above its former sibling (fine, since is the smaller) and above (fine, since ), and moves the possible violation one level down.
Cost. A complete binary tree with nodes has height , and each loop moves one level, doing work per level (sift-down makes two comparisons per level). The minimum is always at index 0, so peek is .
∎
import random
class MinHeap:
def __init__(self):
self.a = []
def __len__(self):
return len(self.a)
def peek(self):
return self.a[0]
def push(self, x):
a = self.a
a.append(x)
i = len(a) - 1
while i > 0: # sift up
parent = (i - 1) // 2
if a[parent] <= a[i]:
break
a[parent], a[i] = a[i], a[parent]
i = parent
def pop(self):
a = self.a
top = a[0]
last = a.pop() # remove the last leaf...
if a:
a[0] = last # ...and put it at the root
i, n = 0, len(a)
while True: # sift down
smallest = i
for child in (2 * i + 1, 2 * i + 2):
if child < n and a[child] < a[smallest]:
smallest = child
if smallest == i:
break
a[i], a[smallest] = a[smallest], a[i]
i = smallest
return top
def is_valid(self):
return all(self.a[(i - 1) // 2] <= self.a[i] for i in range(1, len(self.a)))
h = MinHeap()
for x in [9, 4, 12, 2, 6, 3, 8, 5, 10]:
h.push(x)
print("array after pushes:", h.a, "valid:", h.is_valid())
print("pops:", [h.pop() for _ in range(4)], "array now:", h.a, "valid:", h.is_valid())
rng = random.Random(42)
data = [rng.randint(0, 999) for _ in range(5000)]
h = MinHeap()
for x in data:
h.push(x)
assert [h.pop() for _ in range(len(data))] == sorted(data)
print("5000 random pushes and pops come out sorted")Building a heap in linear time, and heapsort
Given items at once, we could push them one by one for . Robert Floyd observed in 1964 that we can do better by working bottom-up: put the items in the array in any order, then call sift-down on every internal node, starting from the last one, index , and moving backwards to the root. When we sift down node , both of its subtrees are already heaps (we processed them earlier), so after the sift-down, the subtree at is a heap too. After the root, the whole array is a heap.
Theorem— Heapify is linear
Bottom-up heapify of items takes time.
Proof
Sifting down a node whose subtree has height costs at most for some constant . In a complete binary tree with nodes, at most nodes have height : half the nodes are leaves (height 0), a quarter have height at most 1, and so on. The total cost is therefore at most
using the series at (see sequences and series). So heapify is .
∎
The intuition: most nodes live near the bottom, and in bottom-up heapify they move down a short distance. Pushing one by one is the opposite: most items arrive at the bottom and may have to travel all the way up. Python's heapq.heapify is the linear-time version.
Heapsort (J. W. J. Williams, 1964) sorts in place with a max-heap: heapify the array, then repeatedly swap the root (the maximum) with the last item of the heap, shrink the heap by one, and sift the new root down. The sorted suffix grows from the right. It runs in in the worst case with extra memory, which no other simple sort guarantees, but it is not stable and its jumps between distant array positions are unkind to caches. In practice heapsort is a safety net: introsort, the usual implementation of C++'s std::sort, runs quicksort and switches to heapsort if the recursion gets suspiciously deep. Python's own sorted uses a different, stable algorithm (see Searching and sorting).
def sift_down(a, i, n, counter):
"""Max-heap sift-down of a[i] within a[:n]; counter[0] counts comparisons."""
while True:
largest = i
for child in (2 * i + 1, 2 * i + 2):
if child < n:
counter[0] += 1
if a[child] > a[largest]:
largest = child
if largest == i:
return
a[i], a[largest] = a[largest], a[i]
i = largest
def heapify(a, counter):
for i in range(len(a) // 2 - 1, -1, -1):
sift_down(a, i, len(a), counter)
def push_all(items, counter):
a = []
for x in items:
a.append(x)
i = len(a) - 1
while i > 0:
counter[0] += 1
parent = (i - 1) // 2
if a[parent] >= a[i]:
break
a[parent], a[i] = a[i], a[parent]
i = parent
return a
def heapsort(a):
counter = [0]
heapify(a, counter)
for end in range(len(a) - 1, 0, -1):
a[0], a[end] = a[end], a[0] # the maximum joins the sorted suffix
sift_down(a, 0, end, counter)
return a
print(" n heapify comps/n push-one-by-one comps/n")
for n in [1_000, 10_000, 100_000]:
worst = list(range(n)) # increasing input: every push climbs to the root
c1, c2 = [0], [0]
heapify(worst[:], c1)
push_all(worst, c2)
print(f"{n:7,} {c1[0] / n:14.2f} {c2[0] / n:22.2f}")
print(heapsort([31, 4, 15, 9, 26, 5, 35, 8, 97, 93]))The comparisons per item for heapify level off at about 2 however large gets (with two comparisons per level, the proof's bound works out to ), while pushing one by one grows like , exactly as the theorem predicts.
The heapq module and the problems it solves
Python's heapq module is not a class: it is a set of functions that treat an ordinary list as a binary min-heap. heappush(h, x) and heappop(h) are push and pop; h[0] peeks; heapify(h) is the linear-time build; heappushpop and heapreplace combine a push and a pop in one sift; nsmallest, nlargest and merge solve the problems below. Because it is a plain list, you can inspect it, but you must only modify it through these functions.
Three practical idioms come up constantly:
- Max-heaps. Push
-priorityinstead ofpriority, or push objects whose comparison is reversed. (Python 3.14 addedheappush_max,heappop_maxand friends; code that must run on older versions still uses negation.) - Ties and incomparable items. Entries are usually tuples
(priority, tiebreak, item). If two priorities are equal, Python compares the next element; if that were the item itself and items are not comparable (dicts, say), you would get aTypeError. A counter that increases with every push makes ties resolve first-in-first-out and never reaches the item. - Changing a priority. A binary heap cannot find an arbitrary item quickly, so
heapqhas nodecrease_key. The standard workaround is lazy deletion: push a new entry with the new priority and remember (in a dict or a flag on the old entry) that the old one is stale; when a stale entry is popped, discard it and pop again. The heap may grow with stale entries, but each is pushed and popped once, so the total cost stays amortised per operation. Dijkstra's algorithm uses exactly this pattern.
For priority queues shared between threads, use queue.PriorityQueue, which wraps heapq with a lock.
Example— Top k of a stream
To find the largest values in a stream of , keep a min-heap of the best seen so far. For each new value, if the heap has fewer than items, push it; otherwise, if the value beats the heap's minimum (the weakest of the current top ), replace the minimum with it. The invariant the heap holds the largest values seen so far is preserved at every step, because a value that cannot beat the weakest of the current top cannot be in the top . Cost: time and memory, so it works on a stream too large to store. This is what heapq.nlargest does.
Example— Merging k sorted lists
Fifty servers each write a log sorted by timestamp; we want one sorted log. Put the first entry of each list in a min-heap, along with which list it came from. Repeatedly pop the smallest, output it, and push the next entry from the same list. The heap never holds more than entries, so merging entries in total costs . The same step is the heart of external sorting, which sorts data larger than memory by sorting chunks that fit, writing them out as sorted runs, and merging the runs; databases and large data pipelines do this every day. heapq.merge does it lazily, reading each input only as needed.
Example— Scheduling events
A discrete-event simulation (or an event loop) keeps future events in a heap keyed by time: pop the earliest, run it, and push whatever events it schedules. Python's sched module and the asyncio event loop (base_events.py) both keep their timers in a heapq heap.
import heapq, itertools
# Top 3 scores in a programming contest, read as a stream, with a size-3 min-heap.
stream = [("Aiyana", 71), ("Bongani", 88), ("Chiara", 64), ("Dmitri", 93),
("Esi", 79), ("Farid", 85), ("Grace", 97), ("Hiroshi", 58)]
top = []
for name, score in stream:
if len(top) < 3:
heapq.heappush(top, (score, name))
elif score > top[0][0]:
heapq.heapreplace(top, (score, name)) # pop the weakest, push the newcomer, one sift
print("top 3:", sorted(top, reverse=True))
print("same: ", heapq.nlargest(3, stream, key=lambda ns: ns[1]))
# Merge three sorted logs by hand, then with heapq.merge.
logs = {"web": [1, 4, 9, 12], "db": [2, 3, 10], "cache": [5, 6, 7, 11]}
heap = [(entries[0], name, 0) for name, entries in logs.items()]
heapq.heapify(heap)
merged = []
while heap:
t, name, i = heapq.heappop(heap)
merged.append((t, name))
if i + 1 < len(logs[name]):
heapq.heappush(heap, (logs[name][i + 1], name, i + 1))
print("merged:", merged)
assert [t for t, _ in merged] == list(heapq.merge(*logs.values()))
# A tiny clinic simulation: patients arrive with an urgency (1 = most urgent);
# whenever a doctor is free, the most urgent waiting patient (earliest arrival on ties) is seen.
arrivals = [(0, "Amaka", 3), (1, "Bilal", 1), (2, "Chen", 2), (2, "Dalia", 1), (3, "Emre", 3)]
waiting, counter, clock, seen = [], itertools.count(), 0, []
for t, name, urgency in arrivals:
heapq.heappush(waiting, (urgency, next(counter), name))
if t >= clock: # the doctor is free: see someone (15 time units each)
_, _, who = heapq.heappop(waiting)
seen.append(who)
clock = t + 15
while waiting:
seen.append(heapq.heappop(waiting)[2])
print("order seen:", seen)Tournaments, tapes and today's libraries
A heap is a sports tournament in disguise. In a knockout bracket each match sends the winner up a level, and the champion sits at the top; a heap keeps the same shape, but when the champion leaves, the runners-up play again only along one path, which is why the next champion costs just matches. That is how François Pinard explains heaps in the essay at the end of heapq.py, which also recalls their first big industrial job: sorting data on magnetic tape. A heap holding as many records as memory allows can emit a sorted run while still accepting new records that fit after the last one written, a technique called replacement selection; on random input its runs come out about twice as long as memory, which halves the merging work.
The binary heap itself was published by J. W. J. Williams in 1964 as part of heapsort, and Robert Floyd gave the linear-time construction the same year. Every mainstream language ships one: Java's PriorityQueue, C++'s std::priority_queue, Go's container/heap, and Python's heapq. High-performance code sometimes uses -ary heaps (each node with 4 or 8 children): the tree is shallower, so pushes are cheaper, and the children of a node sit side by side in one cache line.
Common misconceptions
Misconception
"A heap is a sorted array." Only each root-to-leaf path is sorted. In the figure, 5 at index 1 is larger than 3 and 4 at indices 2 and 5. A sorted array is a valid heap, but most heaps are not sorted. To get sorted output you must pop repeatedly, which is heapsort.
Misconception
"h[1] is the second smallest item." The second smallest is one of the root's children, so it is h[1] or h[2]. Beyond that, the -th smallest can be anywhere in the first positions.
Misconception
"Removing an arbitrary item from a heap is O(log n)." Repairing the heap after removing position is , but finding the item is , since the heap gives no help with searching. Libraries that support decrease_key keep a separate dict from items to positions and update it on every swap; heapq users usually prefer lazy deletion.
Misconception
"Fibonacci heaps make everything faster." Fibonacci heaps (Fredman and Tarjan, 1987) improve the theoretical bound of Dijkstra's algorithm with an amortised decrease_key, but their constant factors and pointer-heavy layout make them slower than a binary or 4-ary array heap on real inputs. Measure before switching.
Exercises
1. Heaps and priority queues
Warm-upHumanA binary heap is stored in a Python list with the root at index 0. What is the index of the parent of the item at index 10?
2. Heaps and priority queues
Warm-upHumanWhich of these Python lists are valid binary min-heaps (root at index 0)? Select all that apply.
3. Heaps and priority queues
CoreHumanThe list h = [2, 5, 3, 9, 6, 4, 8] is a min-heap. After heapq.heappop(h) returns 2, what does h contain? Write the items in order, separated by spaces (for example 1 2 3).
4. Heaps and priority queues
CoreHumanBottom-up heapify calls sift-down on about nodes, and a sift-down can cost up to swaps. Why is the total nevertheless rather than ?
5. Heaps and priority queues
CoreComputationalA weather station sends temperature readings one at a time. After each reading it must report the median of all readings so far: the middle value if the count is odd, or the mean of the two middle values if it is even.
Write running_medians(readings) that returns the list of medians after each reading. Use two heaps: a max-heap holding the smaller half (store negated values in a heapq list) and a min-heap holding the larger half, kept within one item of each other in size. Each reading should cost .
6. Heaps and priority queues
CoreComputationalA print shop has k identical printers, all free at time 0. Jobs arrive in a list of durations and must be started in list order: each job goes to the printer that becomes free earliest (if several are free at the same time, the one with the lowest number), and starts as soon as that printer is free.
Write schedule(durations, k) that returns a pair (finish_time, assignment): the time at which the last job finishes, and the list of printer numbers (0 to k − 1) that the jobs were given. Use a heap so that each job costs .
7. Heaps and priority queues
StretchHumanA delivery app keeps drivers in a heapq heap of (estimated_arrival, driver_id) entries. A driver's estimate improves from 14 minutes to 9. Which approach keeps every operation amortised and the answers correct?
Further reading and resources
- heapq — Heap queue algorithm · Python documentationThe module reference, with notes on priority-queue implementation details such as tie-breaking and removing entries.
- CPython source: Lib/heapq.pyShort and readable, with an essay by François Pinard on heaps, tournaments and sorting on tape.
- Algorithm 245: Treesort 3 · Robert W. Floyd · 1964The bottom-up construction that builds a heap in linear time.
- Fibonacci heaps and their uses in improved network optimization algorithms · Michael L. Fredman and Robert E. Tarjan · 1987
- sched — Event scheduler · Python documentation
- queue.PriorityQueue · Python documentation
- Open Data Structures · Pat Morin