Skip to content
LumenaryAcademy
Core 55 min

Heaps and priority queues

Always knowing what comes next — the smallest, the most urgent, the earliest — for the price of a logarithm.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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 O(1)O(1) but must scan everything to find the minimum, O(n)O(n). A sorted list finds the minimum instantly but inserts in O(n)O(n). A balanced search tree manages O(log⁡n)O(\log n) for both, but carries pointers, colours and rotations for an ordering we mostly don't need. The binary heap does both in O(log⁡n)O(\log n), peeks at the minimum in O(1)O(1), can be built from nn items in O(n)O(n), and lives in a plain array with no pointers at all.

DefinitionsH

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.

2539648121025396481210012345678
A min-heap of nine keys drawn as a tree (top) and stored as an array (bottom). The children of index i are at 2i + 1 and 2i + 2: for example, 5 at index 1 has children 9 and 6 at indices 3 and 4.
ExplanationH

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 O(log⁡n)O(\log n) time on a heap of nn items. peek takes O(1)O(1).

Proof

Sift up. Invariant: the heap property holds for every parent–child pair except possibly the pair formed by the moving item xx and its current parent pp. Initially the only new pair is xx with its parent, so the invariant holds. If p>xp > x, swap them. Now xx's pair with its new children is fine: one child is p>xp > x, and the other was a child of pp before, so it is ≥p>x\ge p > x. And pp, moved down, sits above nodes that were all in its subtree before, which were all ≥p\ge p. So the only possibly broken pair is again xx with its new parent, one level up. The loop stops when xx reaches the root or its parent is ≤x\le x, and then nothing is broken.

Sift down is symmetric: the only possibly broken pairs are between the moving item xx and its children. Swapping xx with its smaller child cc puts cc above its former sibling (fine, since cc is the smaller) and above xx (fine, since c<xc < x), and moves the possible violation one level down.

Cost. A complete binary tree with nn nodes has height ⌊log⁡2n⌋\lfloor \log_2 n \rfloor, and each loop moves one level, doing O(1)O(1) work per level (sift-down makes two comparisons per level). The minimum is always at index 0, so peek is O(1)O(1).

∎

python
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")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
ExplanationH

Building a heap in linear time, and heapsort

Given nn items at once, we could push them one by one for O(nlog⁡n)O(n \log n). 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 ⌊n/2⌋−1\lfloor n/2 \rfloor - 1, and moving backwards to the root. When we sift down node ii, both of its subtrees are already heaps (we processed them earlier), so after the sift-down, the subtree at ii is a heap too. After the root, the whole array is a heap.

Theorem— Heapify is linear

Bottom-up heapify of nn items takes O(n)O(n) time.

Proof

Sifting down a node whose subtree has height hh costs at most c⋅hc \cdot h for some constant cc. In a complete binary tree with nn nodes, at most ⌈n/2h+1⌉\lceil n / 2^{h+1} \rceil nodes have height hh: half the nodes are leaves (height 0), a quarter have height at most 1, and so on. The total cost is therefore at most

∑h=0⌊log⁡2n⌋⌈n2h+1⌉c h  ≤  c n∑h≥0h2h  =  2c n,\sum_{h=0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil c\,h \;\le\; c\,n \sum_{h \ge 0} \frac{h}{2^{h}} \;=\; 2c\,n,

using the series ∑h≥0hxh=x/(1−x)2\sum_{h \ge 0} h x^h = x/(1-x)^2 at x=12x = \tfrac12 (see sequences and series). So heapify is O(n)O(n).

∎

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 O(nlog⁡n)O(n \log n) in the worst case with O(1)O(1) 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).

python
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]))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The comparisons per item for heapify level off at about 2 however large nn gets (with two comparisons per level, the proof's bound works out to 2n2n), while pushing one by one grows like log⁡2n\log_2 n, exactly as the theorem predicts.

ExplanationH

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 -priority instead of priority, or push objects whose comparison is reversed. (Python 3.14 added heappush_max, heappop_max and 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 a TypeError. 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 heapq has no decrease_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 O(log⁡n)O(\log n) 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 kk largest values in a stream of nn, keep a min-heap of the best kk seen so far. For each new value, if the heap has fewer than kk items, push it; otherwise, if the value beats the heap's minimum (the weakest of the current top kk), replace the minimum with it. The invariant the heap holds the kk largest values seen so far is preserved at every step, because a value that cannot beat the weakest of the current top kk cannot be in the top kk. Cost: O(nlog⁡k)O(n \log k) time and O(k)O(k) 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 kk entries, so merging NN entries in total costs O(Nlog⁡k)O(N \log k). 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.

python
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)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
History & global context

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 log⁡2n\log_2 n 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 dd-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 misconceptionsH

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 kk-th smallest can be anywhere in the first 2k−12^k - 1 positions.

Misconception

"Removing an arbitrary item from a heap is O(log n)." Repairing the heap after removing position ii is O(log⁡n)O(\log n), but finding the item is O(n)O(n), 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 O(1)O(1) 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

Exercises

1. Heaps and priority queues

Warm-upHuman

A 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-upHuman

Which of these Python lists are valid binary min-heaps (root at index 0)? Select all that apply.

Choose all that apply

3. Heaps and priority queues

CoreHuman

The 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

CoreHuman

Bottom-up heapify calls sift-down on about n/2n/2 nodes, and a sift-down can cost up to log⁡2n\log_2 n swaps. Why is the total nevertheless O(n)O(n) rather than O(nlog⁡n)O(n \log n)?

Choose one

5. Heaps and priority queues

CoreComputational

A 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 O(log⁡n)O(\log n).

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Heaps and priority queues

CoreComputational

A 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 O(log⁡k)O(\log k).

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Heaps and priority queues

StretchHuman

A 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 O(log⁡n)O(\log n) amortised and the answers correct?

Choose one

Further reading and resources