Heaps & Priority Queues

The priority queue ADT

A priority queue is an abstract data type (a contract, not an implementation) holding items with priorities. It supports insert (add an item), peek (look at the highest-priority item), and pop (remove and return it). A min-priority queue treats the smallest key as most urgent; a max-priority queue the largest. Unlike a queue from M22, arrival order does not matter, only priority.

Where they show up: operating-system and job schedulers, network routers (quality of service), Dijkstra's shortest paths and A* search (M31), Huffman coding, event-driven simulation, "the k largest" anything, and merging sorted files that do not fit in memory.

A heap wins because it maintains less order than a BST. It does not know the second-smallest item's exact position or support sorted iteration; it only guarantees the minimum is on top. Doing less work is why it is faster and why it fits in a flat array.

The binary heap and its array layout

A binary min-heap is a binary tree with two invariants:

1. Shape: it is a complete binary tree (every level full except the last, which fills left to right).
2. Heap order: every node is ≤ its children. So the root holds the minimum, and every path from the root downward is non-decreasing. Siblings are in no particular order.

Because the tree is complete, there are no gaps when you write it out level by level, so it lives in a plain list with no pointers at all. With 0-based indexes:

parent(i) = (i - 1) // 2
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2

A complete tree with n nodes has height ⌊log₂ n⌋, which is where every O(log n) below comes from. The array layout also has excellent cache locality, and it is why heapq can operate on any ordinary list you hand it.

Sift up and sift down

Both operations temporarily break heap order in one place, then repair it along a single root-to-leaf path:

• Push: append the item at the end (keeps the shape), then sift up: while the item is smaller than its parent, swap them. At most height swaps.
• Pop: the minimum is at index 0. Move the last item to the root (keeps the shape), then sift down: while it is larger than its smaller child, swap with that child. Always pick the smaller child, or the new parent would be larger than its other child.

Push and pop values in the visualizer and watch the tree and array views change together. Switch the heap kind to see the max-heap mirror image.

Step through a single pop. Watch i descend and smallest pick the smaller child each round.

Heapify in O(n): why it is faster than n pushes

Turning an arbitrary list into a heap by pushing items one at a time costs O(n log n). The bottom-up heapify algorithm does better: leaves are already valid one-element heaps, so start at the last internal node (n // 2 - 1) and sift each node down, moving toward the root.

The intuition for O(n): a node's sift-down costs at most its height. Half the nodes are leaves (height 0, cost 0), a quarter have height 1, an eighth height 2, and only the root has height log n. The total work is n · (0/2 + 1/4 + 2/8 + 3/16 + …), and that series converges to n. Most nodes are near the bottom, and the bottom is cheap. Pushing one at a time is the opposite: most items are inserted when the heap is already large, and each may sift up the full height.

Heapify's swap count grows linearly (about n); the push-one-at-a-time count grows like n log n.

The heapq module

heapq implements a binary min-heap on top of a regular list. There is no heap class: you keep a list and pass it to functions. The functions are written in C and are much faster than a Python implementation.

Heap entries: tuples, tie-breakers, and dataclasses

Real priority queues hold things with priorities: tasks, events, graph nodes. The standard trick is to push tuples, because tuples compare element by element: (priority, item) sorts by priority first. But when two priorities are equal, Python compares the items, which can fail or give surprising orders.

The fix is a tie-breaker: a monotonically increasing counter as the second element. Equal priorities then come out in insertion order (FIFO, which makes the queue stable), and the item itself is never compared.

For richer entries use @dataclass(order=True), which generates comparison methods from the fields in order, and exclude the payload with field(compare=False):

Heap patterns: top-k, k-way merge, running median

Top-k

To keep the k largest items from a stream of n, maintain a min-heap of size k. Its root is the smallest of the current top k, the "bar to beat". Each new item either loses to the bar (O(1) check) or replaces it (O(log k)). Total O(n log k) time and O(k) memory, so it works on streams far larger than memory. heapq.nlargest does exactly this; for k = 1 use max(), and when k is close to n just sort.

Merging k sorted lists

Put the first element of each list in a heap together with which list it came from. Pop the smallest, output it, and push the next element from the same list. Each of the N total elements is pushed and popped once in a heap of size k: O(N log k). This is how databases and sort merge sorted runs that do not fit in memory, and heapq.merge does it lazily.

Running median with two heaps

Keep the smaller half of the numbers in a max-heap and the larger half in a min-heap, with sizes differing by at most one. The median is then at one or both roots: O(log n) per insert, O(1) per query. With Python 3.14 the lower half can use the _max functions directly.

Scheduling, event simulation, and a heapsort preview

A discrete-event simulation keeps a priority queue of future events keyed by time. The loop pops the earliest event, advances the clock to it, and handles it, which may schedule more events. Nothing happens between events, so the simulation jumps straight from one to the next. Bank queues, network protocols, and asyncio's timer handling (call_later) all use a time-ordered heap.

Heapsort falls out immediately: heapify the array in O(n), then pop n times in O(n log n). Done in place (swap the root with the last element of the shrinking heap), it sorts with O(1) extra memory and a guaranteed O(n log n) worst case. It is not stable and has poor cache behavior, which is why Python's sorted uses Powersort instead. You will study it properly in M29; watch it here:

Pitfalls

• A heap is not sorted. h[1] is not the second smallest; only h[0] is meaningful. To see items in order, pop them or use sorted(h).
• Forgetting to heapify. heappop on an arbitrary list returns h[0], not the minimum, and silently leaves garbage. Call heapify once first.
• Mutating items in place after pushing them breaks the invariant without any error. Push a new entry instead (lazy deletion).
• Uncomparable payloads on ties raise TypeError. Use a counter tie-breaker or field(compare=False).
• Mixing min and max functions on the same list. heappush on a list maintained by heapify_max corrupts it. One list, one ordering.
• Using a heap for membership tests. x in h is O(n). Pair the heap with a set or dict if you need lookup.
• queue.PriorityQueue is a thread-safe wrapper around heapq with locking overhead. Use it only to pass work between threads; otherwise use heapq directly.

Practice

def children(i, n):
    return [j for j in (2 * i + 1, 2 * i + 2) if j < n]

def is_min_heap(a):
    return all(a[(i - 1) // 2] <= a[i] for i in range(1, len(a)))

class MinHeap:
    def __init__(self):
        self.a = []

    @classmethod
    def from_list(cls, items):
        h = cls()
        h.a = list(items)
        for i in range(len(h.a) // 2 - 1, -1, -1):
            h._sift_down(i)
        return h

    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 and a[i] < a[(i - 1) // 2]:
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p

    def pop(self):
        if not self.a:
            raise IndexError("pop from empty heap")
        last = self.a.pop()
        if not self.a:
            return last
        top, self.a[0] = self.a[0], last
        self._sift_down(0)
        return top

    def _sift_down(self, i):
        a, n = self.a, len(self.a)
        while True:
            s, l, r = i, 2 * i + 1, 2 * i + 2
            if l < n and a[l] < a[s]:
                s = l
            if r < n and a[r] < a[s]:
                s = r
            if s == i:
                return
            a[i], a[s] = a[s], a[i]
            i = s

import heapq
from collections import Counter

def top_k_words(words, k):
    counts = Counter(words)
    best = heapq.nsmallest(k, counts.items(), key=lambda kv: (-kv[1], kv[0]))
    return [word for word, _ in best]

import heapq

def merge_sorted(lists):
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        value, i, j = heapq.heappop(heap)
        out.append(value)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out

import heapq

class RunningMedian:
    def __init__(self):
        self.low = []
        self.high = []

    def add(self, x):
        if not self.low or x <= self.low[0]:
            heapq.heappush_max(self.low, x)
        else:
            heapq.heappush(self.high, x)
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, heapq.heappop_max(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush_max(self.low, heapq.heappop(self.high))

    def median(self):
        if not self.low:
            raise ValueError("no data")
        if len(self.low) > len(self.high):
            return self.low[0]
        return (self.low[0] + self.high[0]) / 2

Mini-project: a task scheduler with priorities and aging

pixi init scheduler && cd scheduler
pixi add python=3.14 pytest
pixi run python -m pytest -q

Quiz

Recap

• A priority queue supports insert, peek, and pop-most-urgent; a binary heap does them in O(log n), O(1), O(log n), and builds in O(n).
• A heap is a complete tree stored in a list: children at 2i + 1, 2i + 2; parent at (i - 1) // 2.
• Push sifts up from the end; pop moves the last item to the root and sifts down toward the smaller child.
• heapq is a min-heap over a list. Python 3.14 adds heapify_max, heappush_max, heappop_max, heappushpop_max, and heapreplace_max.
• Use (priority, counter, item) or dataclass(order=True) with field(compare=False) for stable, safe entries.
• Patterns: size-k min-heap for top-k, k-way merge, two heaps for medians, time-ordered heaps for simulation.

Going further

• heapq: heap queue algorithm, including the priority-queue implementation notes
• What's new in Python 3.14
• queue.PriorityQueue for threads
• dataclasses: order=True and field(compare=False)
• Next: M26 Graphs, where heaps power Dijkstra's algorithm later in M31.