9 — Heaps and priority queues

A priority queue is a container that always hands back its smallest (or largest) item next, whatever order the items arrived in. The binary heap is the standard way to build one: an array that represents a complete binary tree, kept just ordered enough that the minimum is always at index 0. “Just ordered enough” is the point. A sorted array also gives the minimum in O(1), but inserting into it costs O(n); a heap does insert and remove-minimum in O(log n) by maintaining a much weaker invariant.

Priority queues schedule the next event in a simulation, the next timer in an event loop and the next process in an operating system. They pick the next vertex in Dijkstra’s and Prim’s algorithms, merge sorted runs in external sorting and database query execution, and keep the k best results in a search engine. Many problems that look like they need sorting only need repeated access to the current minimum, and a heap does that for less.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ on other machines; the ratios and growth patterns are what matter.

The priority queue abstract data type

A heap is the balanced choice when pushes and pops are interleaved. If all pushes come first and all pops after, sorting once is just as good. If only the minimum is ever needed once, min() is O(n) and needs no structure at all.

The order among equal priorities is not defined. Binary heaps are not stable: two items with the same priority can come out in either order unless a tie-breaker is added, which matters in schedulers and in Python, where the tie-breaker is also needed to avoid comparing items that cannot be compared (see below).

The binary heap

The shape: a complete tree stored in an array

A binary heap is a complete binary tree: every level is full except possibly the last, which is filled from the left. A complete tree has no gaps, so it can be stored in an array level by level with no pointers at all. For the node at index i (0-based):

$\text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor \qquad \text{left}(i) = 2i+1 \qquad \text{right}(i) = 2i+2$

array:  index  0  1  2  3  4  5
               1  3  2  5  9  8

tree:              1          (0)
                 /   \
               3       2      (1) (2)
              / \     /
             5   9   8        (3) (4) (5)

A complete tree with n nodes has height $\lfloor \log_2 n \rfloor$, so any root-to-leaf path has O(log n) nodes. That is where every logarithm in this chapter comes from. The leaves are exactly the indices from $\lfloor n/2 \rfloor$ to n − 1, half the array.

The invariant: heap order

In a min-heap, every node is less than or equal to its children. By induction, every node is less than or equal to everything in its subtree, so the root is the minimum. A max-heap reverses the comparison.

Heap order is much weaker than sorted order. It says nothing about siblings, or about nodes in different subtrees: in the heap above, 3 is at depth 1 while the smaller 2 is beside it, and 5 at depth 2 is smaller than 8 at the same depth. Many different arrays are valid heaps of the same values. That weakness is what makes heap updates cheap: an update only has to repair order along one path.

Sift up (push)

To insert, append the new item at the end of the array (the next free leaf position, which keeps the tree complete), then repair the order along its path to the root: while the item is smaller than its parent, swap them.

push 0 into [1, 3, 2, 5, 9, 8]

append at index 6:         1               parent of 6 is 2: 0 < 2, swap
                         /   \
                       3       2
                      / \     / \
                     5   9   8   0

after one swap:            1               parent of 2 is 0: 0 < 1, swap
                         /   \
                       3       0
                      / \     / \
                     5   9   8   2

after two swaps:           0               at the root: stop
                         /   \
                       3       1
                      / \     / \
                     5   9   8   2

array: [0, 3, 1, 5, 9, 8, 2]

At most one swap per level, so push is O(log n) worst case. Only the path from the new leaf to the root changes, and along that path the values move down by one level each, which preserves order with their other children (they were already smaller than everything below them). On random input, sift-up is O(1) on average, because half of all nodes are leaves and a random new value usually belongs near the bottom.

Sift down (pop)

To remove the minimum, take the root, move the last element of the array into the root position (keeping the tree complete), then repair downward: while the item is larger than its smaller child, swap it with that child.

pop from [0, 3, 1, 5, 9, 8, 2]

remove 0, move last (2) to the root:      2          smaller child is 1: 2 > 1, swap
                                        /   \
                                      3       1
                                     / \     /
                                    5   9   8

after one swap:                           1          smaller child of 2 is 8: 2 < 8, stop
                                        /   \
                                      3       2
                                     / \     /
                                    5   9   8

array: [1, 3, 2, 5, 9, 8]

Swapping with the smaller child is essential: that child becomes the parent of the other one, so it must be the smaller of the two. Pop is O(log n) worst case and, unlike push, usually costs close to the full height on random data, because the element moved to the root came from the bottom and tends to sink back there.

Implementation

class MinHeap:
    def __init__(self, items=()):
        self._a = list(items)
        self._heapify()

    def __len__(self):
        return len(self._a)

    def peek(self):
        return self._a[0]

    def push(self, x):
        self._a.append(x)
        self._sift_up(len(self._a) - 1)

    def pop(self):
        a = self._a
        last = a.pop()                      # IndexError if empty
        if not a:
            return last
        top = a[0]
        a[0] = last                         # move the last leaf to the root
        self._sift_down(0)
        return top

    def _sift_up(self, i):
        a = self._a
        x = a[i]
        while i > 0:
            parent = (i - 1) // 2
            if a[parent] <= x:
                break
            a[i] = a[parent]                # move the parent down
            i = parent
        a[i] = x

    def _sift_down(self, i):
        a, n = self._a, len(self._a)
        x = a[i]
        while True:
            child = 2 * i + 1
            if child >= n:
                break
            if child + 1 < n and a[child + 1] < a[child]:
                child += 1                  # the smaller child
            if x <= a[child]:
                break
            a[i] = a[child]                 # move the child up
            i = child
        a[i] = x

    def _heapify(self):
        for i in reversed(range(len(self._a) // 2)):   # last internal node down to root
            self._sift_down(i)

Instead of swapping at each step, the sifts hold the moving value in x, shift the others by one assignment each, and write x once at the end, which halves the writes. The implementation was checked against heapq on 500 random sequences of interleaved pushes and pops, with the heap property verified after every operation.

Heapify in O(n)

There are two ways to build a heap from n items. Pushing them one at a time costs O(log n) each, O(n log n) in the worst case. Bottom-up heapify, due to Robert Floyd (1964), does better: treat the array as a complete tree as it stands, and call sift-down on every internal node from the last one (index $\lfloor n/2 \rfloor - 1$) back to the root. When a node is sifted, both its subtrees are already heaps, so sift-down makes its whole subtree a heap.

heapify [5, 1, 8, 3, 9, 2]           internal nodes: indices 2, 1, 0

start:          5            sift_down(2): 8 > child 2, swap   -> [5, 1, 2, 3, 9, 8]
              /   \          sift_down(1): 1 < children 3, 9  -> no change
            1       8        sift_down(0): 5 > smaller child 1, swap;
           / \     /                       5 > smaller child 3, swap
          3   9   2                                            -> [1, 3, 2, 5, 9, 8]

Why it is linear

Sift-down from a node costs at most its height h (distance to the bottom). In a complete tree with n nodes there are at most $\lceil n / 2^{h+1} \rceil$ nodes of height h. Most nodes are near the bottom and travel almost nowhere; only one node, the root, can travel the full $\log_2 n$. Summing:

$\sum_{h=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^{h+1}} \cdot O(h) \;=\; O\!\left(n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}}\right) \;=\; O(n)$

because $\sum_{h \ge 0} h / 2^{h+1} = 1$. With two comparisons per level (find the smaller child, then compare with it), the total is at most about 2n comparisons. Pushing one at a time has no such saving, because the expensive end is reversed: the many nodes near the bottom are exactly the ones that may travel the full height up.

Measured

Comparisons counted by instrumented versions of both methods:

Heapify’s cost per element is flat, as the proof says, and stays under 2: on descending input (the worst case for building a min-heap, since every node must sink to the bottom), heapify of a million items used 1,999,974 comparisons, just under 2n. Repeated pushes on random input are also close to linear, about 2.3 comparisons per element, because a random new item rarely rises far. On descending input, each new item is the new minimum and climbs to the root, and the per-element cost grows with $\log_2 n$: the O(n log n) worst case.

Wall-clock time with heapq (C implementation) and with the Python class above:

heapify is about twice as fast as pushing random data and almost ten times as fast as pushing adversarial data at a million items. When all the items are available up front, heapify them.

Heapify followed by n pops is heapsort: O(n log n) worst case, in place, not stable. It is covered with the other sorting algorithms in Sorting; in practice its poor cache behavior (sift-down jumps from index i to 2i + 1) makes it slower than quicksort and merge sort, and its main use today is as the fallback that bounds introsort’s worst case.

Python’s heapq

heapq provides functions that treat a plain list as a min-heap, using the same 0-based layout as above:

import heapq

h = [5, 1, 8, 3, 9, 2]
heapq.heapify(h)              # in place, O(n); h is now [1, 3, 2, 5, 9, 8]
heapq.heappush(h, 4)          # O(log n)
smallest = heapq.heappop(h)   # O(log n)
h[0]                          # peek, O(1)
heapq.heappushpop(h, x)       # push then pop, faster than the two calls
heapq.heapreplace(h, x)       # pop then push (the heap must not be empty)

heappushpop returns x immediately if it is no larger than the root, and otherwise does a single sift-down; heapreplace always pops first, so it can return a value larger than x. Both do one sift where separate calls would do two, and they are the inner operation of every bounded-size heap below.

The list is just a list. Nothing stops code from appending to it or sorting it directly, and anything other than the heapq functions (or a full sort, which also produces a valid heap) can break the invariant silently.

Max-heaps: negation, and the 3.14 functions

Until Python 3.14, heapq exposed only min-heap functions, and the standard workaround for a max-heap is to negate the keys:

nums = [5, 1, 8, 3, 9, 2]
h = [-x for x in nums]
heapq.heapify(h)
largest = -heapq.heappop(h)   # 9

Negation works for numbers. For strings or other non-numeric keys it does not, and the older workaround is a wrapper class with a reversed __lt__.

Python 3.14 added public max-heap functions to heapq: heapify_max, heappush_max, heappop_max, heappushpop_max and heapreplace_max. (Earlier versions had some of them only as private, underscore-prefixed helpers used inside the module.) In Python 3.14 here:

>>> h = [5, 1, 8, 3, 9, 2]
>>> heapq.heapify_max(h); h
[9, 5, 8, 3, 1, 2]
>>> heapq.heappop_max(h)
9
>>> h
[8, 5, 2, 3, 1]
>>> heapq.heappush_max(h, 7); h
[8, 5, 7, 3, 1, 2]

These work for any comparable type, with no negation. Code that must run on Python 3.13 or earlier still needs the negation trick. A list must be used consistently with either the min functions or the max functions, never both.

Tuples, ties and tie-breaking counters

Heap items are compared with <. The usual way to attach a payload is a tuple (priority, item), which compares by priority first. When two priorities are equal, Python compares the items, and that fails if they are not comparable:

>>> h = []
>>> heapq.heappush(h, (2, {"name": "b"}))
>>> heapq.heappush(h, (2, {"name": "a"}))
TypeError: '<' not supported between instances of 'dict' and 'dict'

The fix is a unique, increasing tie-breaker between the priority and the payload:

import itertools
counter = itertools.count()
heapq.heappush(h, (priority, next(counter), task))

The counter guarantees that comparisons never reach the payload, and it also makes the heap behave stably: among equal priorities, items come out in insertion order (FIFO). Using a decreasing counter gives LIFO among ties instead. The heapq documentation describes this pattern, together with marking entries as removed for deletion and priority changes; that is the lazy deletion used for Dijkstra below.

nlargest, nsmallest and merge

>>> heapq.nsmallest(3, ["pear", "fig", "banana", "kiwi"], key=len)
['fig', 'pear', 'kiwi']

nlargest(k, iterable, key=None) and nsmallest keep a heap of size k while scanning the input once, O(n log k), and accept a key function. Both are stable (among equal keys, earlier items win), which they achieve by decorating each element with its position; that decoration has a cost, measured below. For k = 1 use min/max, and for k close to n, sorted(...)[:k] is faster, as the documentation itself notes.

heapq.merge(*iterables, key=None, reverse=False) lazily merges already-sorted inputs, O(N log k) for N total items from k inputs, using O(k) memory. It is the k-way merge described below, ready-made.

Top-k and selection

Top K problems ask for the k largest (or smallest, most frequent, closest) of n items. Four approaches:

1. Sort and slice: O(n log n) time. Simple and, in Python, fast because sorted runs in C.
2. Bounded min-heap of size k: keep the k largest seen so far in a min-heap; each new item replaces the root only if it beats the smallest of the current top k. O(n log k) time, O(k) space, works on streams.
3. Heapify all, pop k times: O(n + k log n) time, O(n) space.
4. Quickselect: partition around a pivot like quicksort but recurse into one side only. Expected O(n) time, O(n²) worst case with bad pivots (random pivots make that vanishingly unlikely; median-of-medians guarantees O(n) worst case at a large constant factor). Gives the k-th element and an unordered top k, and needs the whole array in memory.

The bounded heap, the workhorse for streams:

def top_k_heap(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)                     # min-heap of the k largest so far
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)      # pop the smallest, push x
    return sorted(heap, reverse=True)

The invariant: after processing a prefix, heap holds the k largest items of that prefix and heap[0] is the k-th largest. A new item belongs in the top k exactly when it exceeds heap[0]. The early comparison x > heap[0] means most items cost one comparison and no heap operation: on random input, the probability that the i-th item enters the top k is about k/i, so the expected number of heap updates is about $k \ln(n/k)$, far fewer than n.

Quickselect with a three-way partition (which handles duplicates without degrading):

import random

def quickselect(a, k):
    """k-th smallest (0-based) in expected O(n). Does not modify the input."""
    a = list(a)
    lo, hi = 0, len(a) - 1
    while True:
        if lo == hi:
            return a[lo]
        pivot = a[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi              # a[lo:lt] < pivot, a[gt+1:hi+1] > pivot
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        if k < lt:
            hi = lt - 1
        elif k > gt:
            lo = gt + 1
        else:
            return pivot

Both were checked against sorting on 2,000 random arrays with many duplicates. Finding the top k of 1,000,000 random floats (for quickselect, only the k-th largest value):

• For small k, the heap wins by more than 10 times over sorting, because nearly every element is rejected by a single comparison with heap[0].
• At k = 100,000 the heap does real work on many more items, and sorting catches up. nlargest becomes the slowest because of its stability decoration (it builds a tuple per element it keeps). The documentation’s advice to use sorted for large k is borne out.
• Quickselect’s expected O(n) does not beat the C implementations here because every step of its partition loop is interpreted Python. In C, C++ or Rust (std::nth_element, select_nth_unstable), selection is the fastest option for a one-off k-th element on an in-memory array. NumPy exposes it as numpy.partition.

Kth Largest Element

Kth Largest Element in an Array is the bounded heap returning heap[0] instead of the whole heap, O(n log k), or quickselect for k-th largest = (n − k)-th smallest, expected O(n). Kth Largest Element in a Stream must answer after each new item; only the bounded heap applies, since there is no array to partition, and each add costs O(log k).

The k-th smallest is symmetric: a bounded max-heap of size k (negated keys in Python before 3.14, or the _max functions from 3.14) keeps the k smallest, and its root is the k-th smallest.

Top K Frequent Elements and K Closest Points

Top K Frequent Elements: count with a Counter, then heapq.nlargest(k, counts, key=counts.get), O(n + m log k) for m distinct values. Bucket sort by frequency gives O(n) because frequencies are bounded by n. Counter.most_common(k) uses nlargest internally.

K Closest Points to Origin keeps the k smallest distances, so the bounded heap must be a max-heap on distance: its root is the farthest of the current k, the one to evict.

def k_closest(points, k):
    heap = []                               # max-heap by distance, via negation
    for x, y in points:
        d = x * x + y * y                   # squared distance: no sqrt needed
        if len(heap) < k:
            heapq.heappush(heap, (-d, x, y))
        elif d < -heap[0][0]:
            heapq.heapreplace(heap, (-d, x, y))
    return [(x, y) for _, x, y in heap]

>>> sorted(k_closest([(1, 3), (-2, 2), (5, 8), (0, 1)], 2))
[(-2, 2), (0, 1)]

Comparing squared distances avoids the square root and its rounding. Equivalent one-liner: heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2). The common mistake is to use a min-heap of size k, which keeps the k farthest points.

Two heaps: the running median

Find Median from Data Stream: support add(x) and median() as numbers arrive. Sorting after every insert costs O(n log n) per query; keeping a sorted list with bisect.insort costs O(n) per insert because of shifting.

Split the numbers into two halves: a max-heap low holding the smaller half and a min-heap high holding the larger half. Maintain two invariants:

1. Every element of low is ≤ every element of high.
2. len(low) equals len(high) or exceeds it by one.

Then the median is the top of low (odd count) or the average of the two tops (even count), both O(1) to read.

class MedianFinder:
    def __init__(self):
        self._low = []      # max-heap (negated) of the smaller half
        self._high = []     # min-heap of the larger half

    def add(self, x):
        if self._low and x > -self._low[0]:
            heapq.heappush(self._high, x)
        else:
            heapq.heappush(self._low, -x)
        # rebalance so that len(low) == len(high) or len(high) + 1
        if len(self._low) > len(self._high) + 1:
            heapq.heappush(self._high, -heapq.heappop(self._low))
        elif len(self._high) > len(self._low):
            heapq.heappush(self._low, -heapq.heappop(self._high))

    def median(self):
        if len(self._low) > len(self._high):
            return -self._low[0]
        return (-self._low[0] + self._high[0]) / 2

Adding 5, 15, 1, 3, 8 and reading the median after each:

add 5    low [5]          high []          median 5
add 15   low [5]          high [15]        median 10.0
add 1    low [5, 1]       high [15]        median 5
add 3    low [3, 1]       high [5, 15]     median 4.0
add 8    low [5, 3, 1]    high [8, 15]     median 5

(Each heap is shown as its sorted contents.) When 3 arrives, it goes into low, which then has three elements to high’s one, so the largest of low (5) moves to high. Each add is O(log n), each median O(1); the implementation agreed with statistics.median after every insert in 500 random streams.

Pitfalls: inserting into the wrong half breaks invariant 1, so the routing comparison must be against the top of low; and with only the size rebalance (no routing), the halves stay balanced but are no longer ordered.

Sliding Window Median needs deletions of arbitrary elements as the window moves. With heaps that means lazy deletion (record the elements to delete and discard them when they surface at a top, keeping separate counts of valid sizes), O(n log n) overall. A sorted container with O(log n) removal is a cleaner alternative where available. The general two-heap pattern also appears in IPO (maximize capital: a min-heap of projects by cost feeding a max-heap of affordable projects by profit) and in scheduling problems where items move from “not yet available” to “available”.

Merge k sorted lists

Merge k Sorted Lists: merge k sorted sequences with N items in total. Keep a min-heap holding the current head of each sequence. Pop the smallest, output it, and push the next item from the same sequence.

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

>>> merge_k_sorted([[1, 4, 5], [1, 3, 4], [2, 6]])
[1, 1, 2, 3, 4, 4, 5, 6]

The heap never holds more than k items, so each step is O(log k) and the total is O(N log k) time with O(k) extra space. The list index i in each tuple doubles as the tie-breaker, so equal values never cause the comparison to fall through to anything else. For linked lists, store (node.val, i, node); the index keeps Python from comparing ListNode objects, which have no ordering.

Alternatives: concatenating and sorting is O(N log N), which in Python is often faster in practice for in-memory lists because Timsort detects the existing sorted runs. Pairwise divide and conquer (merge lists in pairs, then pairs of results) is also O(N log k) and needs no heap. Merging lists one at a time into an accumulator is O(Nk) and the common slow answer.

The heap merge earns its place when the inputs do not fit in memory or arrive as streams: external sorting sorts chunks that fit in memory, writes them out as runs, and then k-way merges the runs, reading each run sequentially. PostgreSQL’s external sort works this way when a sort exceeds work_mem, and log-structured storage engines merge sorted files the same way during compaction. Related problems: Kth Smallest Element in a Sorted Matrix (each row is a sorted list; pop k times) and Find K Pairs with Smallest Sums (a lazily expanded grid of pair sums).

Reorganize String

Reorganize String: rearrange a string so that no two adjacent characters are equal, or return "" if impossible. It is possible exactly when the most frequent character appears at most $\lceil n/2 \rceil$ times; otherwise there are not enough other characters to separate its copies.

Greedy with a max-heap of counts: at each step, place the most frequent character that is not the one just placed. That character must sit out one step, so hold it aside and push it back after the next placement.

from collections import Counter

def reorganize_string(s):
    heap = [(-count, ch) for ch, count in Counter(s).items()]
    heapq.heapify(heap)
    out = []
    held = None                             # the character used last step, not yet reusable
    while heap:
        count, ch = heapq.heappop(heap)     # most frequent available character
        out.append(ch)
        if held:
            heapq.heappush(heap, held)
            held = None
        if count + 1 < 0:
            held = (count + 1, ch)
    return "".join(out) if len(out) == len(s) else ""

>>> reorganize_string("aaabbc"), reorganize_string("aaab")
('ababac', '')

If the heap empties while a character is still held, the remaining copies cannot be placed and the function returns "". Always choosing the most frequent available character is what makes the greedy safe: it reduces the largest count fastest, so the feasibility condition keeps holding for what remains. The output was checked on 3,000 random strings, both for validity (a permutation with no equal neighbors) and for returning "" exactly when the count condition fails. O(n log σ) for an alphabet of σ characters, which is O(n) for a fixed alphabet.

A heap-free alternative: sort characters by frequency and fill even indices 0, 2, 4, … first, then odd indices. Rearrange String k Distance Apart generalizes the “held” slot to a queue of the last k − 1 characters used.

Task Scheduler

Task Scheduler: tasks are letters; each takes one time unit; two runs of the same task must be at least n units apart (other tasks or idle slots in between). Find the minimum total time.

Simulation with a heap

At each time step, run the available task with the most remaining instances (the same greedy as Reorganize String), and put it in a cooldown queue until it becomes available again:

from collections import Counter, deque

def least_interval_sim(tasks, n):
    heap = [-c for c in Counter(tasks).values()]
    heapq.heapify(heap)
    cooling = deque()                       # (time it becomes available, negated count)
    time = 0
    while heap or cooling:
        time += 1
        if heap:
            c = heapq.heappop(heap) + 1     # run one instance of the most frequent task
            if c < 0:
                cooling.append((time + n, c))
        if cooling and cooling[0][0] == time:
            heapq.heappush(heap, cooling.popleft()[1])
    return time

The cooldown queue is FIFO because every task waits the same n units, so tasks become available in the order they ran. This costs O(T log σ) for T total time steps, and it can also produce the actual schedule.

The formula

Only the count matters, and it has a closed form. Let top be the highest frequency and n_top the number of tasks with that frequency. The most frequent tasks force a frame of top - 1 blocks of length n + 1, followed by one final partial block containing the n_top most frequent tasks:

tasks A A A B B B, n = 2:      top = 3, n_top = 2

A B _ | A B _ | A B            (top - 1) * (n + 1) + n_top = 2 * 3 + 2 = 8

Other tasks fill the idle slots. If there are more tasks than idle slots, no idling is needed at all and the answer is just the number of tasks:

$\text{time} = \max\big(\,\text{len(tasks)},\; (\text{top} - 1)(n + 1) + n_{\text{top}}\big)$

def least_interval_formula(tasks, n):
    counts = Counter(tasks).values()
    top = max(counts)
    n_top = sum(1 for c in counts if c == top)
    return max(len(tasks), (top - 1) * (n + 1) + n_top)

The formula is O(T) for T tasks. Both versions were checked against an exhaustive breadth-first search over all schedules on 1,500 small random inputs, and all three agreed. For AAABBB with n = 2 both return 8. The formula answers this exact problem; the simulation generalizes to variants the formula does not cover, such as tasks with different durations or a required order.

Huffman coding

Huffman coding (David Huffman, 1952) assigns variable-length binary codes to symbols so that frequent symbols get short codes, and no code is a prefix of another, so the bit stream can be decoded without separators. Among all prefix codes that encode one symbol at a time, a Huffman code minimizes the total encoded length.

The algorithm

Put every symbol in a min-heap keyed by frequency. Repeatedly remove the two least frequent subtrees and merge them under a new node whose frequency is their sum. When one tree remains, read each symbol’s code from the path to it: 0 for left, 1 for right.

import heapq, itertools

def huffman_codes(freq):
    """freq: dict symbol -> count. Returns dict symbol -> bit string."""
    if len(freq) == 1:
        (sym,) = freq
        return {sym: "0"}
    tie = itertools.count()                 # tie-breaker: never compare subtrees
    heap = [(count, next(tie), sym) for sym, count in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        c1, _, left = heapq.heappop(heap)   # two least frequent subtrees
        c2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (c1 + c2, next(tie), (left, right)))
    codes = {}
    stack = [(heap[0][2], "")]
    while stack:
        node, prefix = stack.pop()
        if isinstance(node, tuple):
            stack.append((node[0], prefix + "0"))
            stack.append((node[1], prefix + "1"))
        else:
            codes[node] = prefix
    return codes

Without the tie counter, two subtrees with equal counts would be compared directly, which compares a string with a tuple and raises TypeError. A single-symbol input needs a special case, since its tree has no edges and the code would be empty.

On the classic textbook example:

>>> huffman_codes({"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5})
{'d': '111', 'e': '1101', 'f': '1100', 'b': '101', 'c': '100', 'a': '0'}

merges (two smallest each time):
  f:5  + e:9   -> 14
  c:12 + b:13  -> 25
  14   + d:16  -> 30
  25   + 30    -> 55
  a:45 + 55    -> 100

                (100)
               0/    \1
             a:45    (55)
                    0/   \1
                 (25)     (30)
                 0/ \1    0/  \1
               c:12 b:13 (14)  d:16
                         0/ \1
                       f:5  e:9

The total cost is $45 \cdot 1 + (12 + 13 + 16) \cdot 3 + (5 + 9) \cdot 4 = 224$ bits per 100 symbols, against 300 for a fixed 3-bit code. Equivalently, the cost is the sum of all merge totals (14 + 25 + 30 + 55 + 100 = 224), since each merge adds one bit to every symbol beneath it. Ties may be broken differently by other implementations, giving different codes with the same total length.

Why the greedy choice is optimal

Two facts, both provable by exchange arguments. First, in some optimal code the two least frequent symbols are siblings at the deepest level: swapping them into the deepest positions cannot increase the cost, because a less frequent symbol moving deeper and a more frequent one moving shallower never increases the weighted sum. Second, merging those two into one symbol with their combined frequency gives a smaller problem whose optimal solution extends to an optimal solution of the original, with cost exactly the merged frequency higher. Induction on the number of symbols finishes the proof.

Measured on real text

The text is the Python license file shipped with the Python 3.14 installation (LICENSE.txt, 13,804 characters of English legal prose with 76 distinct characters). The encoded text was decoded again and compared with the original to confirm the round trip.

characters 13,804, distinct symbols 76
8-bit encoding: 110,432 bits
fixed-length 7-bit code: 96,628 bits
Huffman: 71,214 bits = 5.159 bits/char (64.5% of 8-bit)
entropy: 5.118 bits/char

Most and least frequent symbols and their codes:

   ' '  2255 111
   'e'  1003 1011
   't'   660 0100
   'n'   607 0010
   'i'   576 0000
   'o'   573 11011
   '?'     1 0110101110010
   'q'     2 0110101110011
   '+'     3 011010111000
max code length 13

Huffman coding cuts the text to 64.5 percent of its 8-bit size and to 74 percent of the best fixed-length code (7 bits for 76 symbols). It comes within 0.041 bits per character of the entropy, $H = -\sum p_i \log_2 p_i = 5.118$ bits, the lower bound for any code that encodes each character independently. Huffman codes always satisfy $H \le L < H + 1$ for the average code length L.

The table needed to decode (the code for each symbol) must also be stored or transmitted, which matters for small inputs. Real compressors go further: DEFLATE (used by gzip, zip and PNG) first replaces repeated strings with back-references (LZ77) and then Huffman-codes the result, and it stores trees compactly as canonical Huffman codes (code lengths only). Arithmetic coding and asymmetric numeral systems (used in Zstandard) beat Huffman’s whole-bit granularity when symbol probabilities are far from powers of 1/2.

d-ary heaps

A d-ary heap gives each node d children instead of 2: the children of node i are $di + 1$ to $di + d$, and the parent is $\lfloor (i-1)/d \rfloor$. The tree is shallower, height $\log_d n$, so sift-up (push, decrease-key) does fewer steps. Sift-down does fewer steps too, but each step must find the smallest of d children, costing d − 1 comparisons, so pop costs about $d \log_d n$ comparisons.

That trade suits workloads with many more pushes or decrease-keys than pops. In Dijkstra’s algorithm with a decrease-key heap there are up to E decrease-keys and only V pops, and choosing $d \approx E/V$ gives $O(E \log_{E/V} V)$, which is better than binary heaps on dense graphs. There is also a hardware argument: with 4 or 8 children per node, all children of a node fit in one or two cache lines, so the shallower tree means fewer cache misses. 4-ary heaps are a common practical choice for this reason.

Pushing 300,000 random floats and then popping them all, with a straightforward Python d-ary heap (tested against sorting):

In this Python implementation, picking the smallest child uses the built-in min over a range, so the per-level interpreter overhead dominates and fewer levels win until d = 16, where scanning children costs more than the levels saved. The precise optimum differs in compiled languages, but the shape (an improvement from 2 to 4, flattening by 8) is typical.

Indexed priority queues, decrease-key and lazy deletion

Dijkstra’s algorithm repeatedly settles the unvisited vertex with the smallest tentative distance, and lowers neighbors’ distances as it goes. The textbook formulation needs decrease-key: lower the priority of an item already in the heap. A plain binary heap cannot do that efficiently, because finding the item is O(n). Two standard solutions:

Indexed priority queue. Keep a position map from each key to its index in the heap array, update it on every swap, and implement decrease-key as “change the priority, then sift up from its position”, O(log n). The heap never holds more than V entries.

class IndexedMinPQ:
    """Binary heap over keys 0..n-1 with decrease_key, via a position map."""

    def __init__(self, n):
        self._heap = []                     # keys, in heap order
        self._pos = [-1] * n                # key -> index in _heap, -1 if absent
        self._prio = [None] * n

    def __len__(self):
        return len(self._heap)

    def __contains__(self, key):
        return self._pos[key] != -1

    def push(self, key, prio):
        self._prio[key] = prio
        self._heap.append(key)
        self._pos[key] = len(self._heap) - 1
        self._up(len(self._heap) - 1)

    def decrease_key(self, key, prio):
        self._prio[key] = prio
        self._up(self._pos[key])

    def pop(self):
        h = self._heap
        top = h[0]
        last = h.pop()
        self._pos[top] = -1
        if h:
            h[0] = last
            self._pos[last] = 0
            self._down(0)
        return top, self._prio[top]

    def _swap(self, i, j):
        h = self._heap
        h[i], h[j] = h[j], h[i]
        self._pos[h[i]] = i
        self._pos[h[j]] = j

    def _up(self, i):
        h, p = self._heap, self._prio
        while i > 0:
            parent = (i - 1) // 2
            if p[h[parent]] <= p[h[i]]:
                break
            self._swap(i, parent)
            i = parent

    def _down(self, i):
        h, p, n = self._heap, self._prio, len(self._heap)
        while True:
            c = 2 * i + 1
            if c >= n:
                break
            if c + 1 < n and p[h[c + 1]] < p[h[c]]:
                c += 1
            if p[h[i]] <= p[h[c]]:
                break
            self._swap(i, c)
            i = c

Lazy deletion. Never decrease a key. Push a new (distance, vertex) entry every time a shorter distance is found, leaving the old entry in the heap, and when an entry is popped whose distance is larger than the vertex’s recorded best, discard it as stale:

def dijkstra_lazy(graph, source):
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                        # stale entry: u was already settled closer
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

The heap can hold up to E entries instead of V, so each operation costs $O(\log E)$ rather than $O(\log V)$, but since $E \le V^2$, $\log E \le 2 \log V$ and the overall bound is still $O((V + E) \log V)$. Both versions were checked against Bellman-Ford on 300 random graphs with zero-weight edges and unreachable vertices. On a random directed graph with 100,000 vertices and 1,000,000 edges:

n=100,000 m=1,000,000 reachable=99,996
lazy heapq: 485 ms, pushes 198,650, stale pops 98,654, max heap 125,364
indexed PQ with decrease-key: 517 ms

Lazy deletion did about twice as many pushes as there are vertices and discarded nearly half its pops as stale, and it was still slightly faster than the indexed queue, because heapq’s sifts run in C while the indexed queue’s position bookkeeping runs in Python. In Python, lazy deletion with heapq is the standard choice. In compiled languages the comparison is closer, and the indexed heap wins when memory is tight or the graph is dense enough that E is much larger than V. The full treatment of Dijkstra, Prim and A* is in Graph algorithms.

Lazy deletion is a general technique, not specific to Dijkstra: any time items in a heap must be removed or updated, mark them (with a set of removed ids, a version number, or by comparing against an authoritative table) and skip them when they reach the top. The max stack in Stacks and queues and the sliding window median use it. The cost is memory for the dead entries and the risk of unbounded growth if they are never popped; a periodic rebuild bounds that.

Other heaps: binomial, Fibonacci and pairing

The binary heap is the right choice in nearly every program. Other heap designs exist mainly to make merging two heaps or decrease-key cheaper, and their advantages are often theoretical.

Fibonacci heaps are famous because they give Dijkstra’s algorithm $O(E + V \log V)$ instead of $O((V + E) \log V)$, which matters asymptotically on dense graphs. In practice they are rarely faster than a binary heap. Each node carries a parent pointer, a child pointer, two sibling pointers, a degree and a mark bit; operations chase pointers across memory; and the O(1) bounds are amortized with large constants. Experimental studies have repeatedly found binary or 4-ary heaps (often with lazy deletion) faster for Dijkstra on real road and web graphs. Their main legacy is theoretical: they established the bound that later, simpler structures try to match in practice.

Pairing heaps are a self-adjusting multiway tree in which merge links two roots and pop-min merges the root’s children in two passes. They are short to implement, merge in O(1), and perform well experimentally, including for decrease-key-heavy workloads. Their exact amortized decrease-key complexity is a long-standing open problem: it is known to be sub-logarithmic, and a lower bound shows it cannot be O(1) for the standard version.

Binomial heaps matter mostly as the conceptual ancestor of Fibonacci heaps and as an example of a mergeable heap with a clean structure. When a program needs mergeable priority queues in practice, a pairing or leftist heap is usually simpler, and when it does not, the binary heap wins.

Other specialized structures solve narrower problems faster: radix heaps and bucket queues (Dial’s algorithm) exploit small integer priorities and monotone extraction for Dijkstra with integer weights; a min-max heap supports both min and max in O(1) peek and O(log n) removal; and a double-ended priority queue can also be built from two heaps with lazy deletion or from a balanced search tree.

Summary