Binary heaps and priority queues

What this chapter covers

A binary heap is the priority queue — the structure for "always give me the most important thing next, and keep doing it as things come and go." It gets there by keeping a much weaker order than a search tree: not fully sorted, just "every parent beats its children," which is enough to guarantee the smallest (or largest) element is always at the root. That weaker promise is cheaper to maintain, so peeking the extreme is O(1) and inserting or removing is O(log n). You met its array-as-tree trick in heapsort; this chapter builds it as a standalone structure and connects it forward to Dijkstra, Huffman coding, and every scheduler.

A bit of history

The binary heap arrived in 1964 with heapsort — J. W. J. Williams introduced the structure specifically to sort, and Robert Floyd immediately showed you could build one in linear time. But the heap outgrew sorting almost at once, because it turned out to be the natural implementation of an idea that predates it: the priority queue, a collection where each element has a priority and you always remove the most urgent. Priority queues were already being used to schedule jobs and drive discrete-event simulations, and the heap gave them an efficient home. The pairing has been standard ever since — when Edsger Dijkstra's shortest-path algorithm needs "the closest unvisited node," or Huffman's compression needs "the two least-frequent symbols," or an operating system needs "the highest-priority ready process," the answer is a binary heap. It's the same structure Williams built to sort, repurposed as the engine of scheduling.

The intuition

A heap is a complete binary tree — filled level by level, left to right, with no gaps — and because it's complete, it packs perfectly into an array with no wasted space and no pointers: the children of index i sit at 2i+1 and 2i+2, and its parent at (i−1)//2. On top of that shape sits one rule, the heap property: every node is less than or equal to its children (for a min-heap). That's a much weaker claim than a search tree's — it says nothing about left versus right, nothing about siblings — but it says the one thing you need: the minimum has no smaller node above it, so the minimum is the root.

Maintaining that rule as elements arrive and leave is two little motions. To insert, drop the new value in the next open leaf and sift it up: while it's smaller than its parent, swap them, climbing until it settles. To remove the minimum, take the root (that's your answer), move the last leaf up to the root to keep the tree complete, and sift it down: while it's bigger than its smaller child, swap with that child, sinking until it settles. Each motion travels at most the height of the tree, log n, so both are O(log n). The weakness of the ordering is the strength of the structure: because you only ever compare along one root-to-leaf path, the heap does far less work than a fully sorted structure to keep its one guarantee.

Complexity: how it scales

Peeking the minimum is $O(1)$ — it's just the root. Push and pop are $O(\log n)$, one sift along a root-to-leaf path. Building a heap from n existing items all at once is $O(n)$, not $O(n \log n)$ — the surprising linear result from the heapsort chapter, because most nodes are near the bottom and barely sift. Space is $O(n)$, and because it's a packed array, that space is tight and cache-friendly. The chart runs a long stream of pushes and pops against heapq:

Both lines are near-linear — n operations at O(log n) each — with heapq about thirteen times faster on the constant, being C.

What it's good at, what it isn't

The heap is the right structure whenever you repeatedly need the most extreme element of a changing set. That covers an enormous amount of ground: greedy algorithms that always take the best available option (Dijkstra, Prim, Huffman), schedulers and event simulators that process the earliest deadline next, top-k queries that keep a heap of the k best seen, and merging many sorted streams by always advancing the one with the smallest front. Its $O(1)$ peek and $O(\log n)$ updates are exactly the profile those problems want, and its packed-array layout makes it fast and compact.

What it isn't is a general search structure. The heap can find the minimum instantly but knows almost nothing about any other element — locating an arbitrary value, or removing one that isn't the extreme, is $O(n)$, because you'd have to scan. It's also not sorted: pop everything and you get sorted order (that's heapsort), but the heap in memory is only partially ordered. If you need ordered iteration, ranges, or arbitrary lookups, that's a balanced search tree, not a heap. The heap trades every capability except one for making that one — grab the extreme — as fast as it can be.

The data, or the inputs

The face-off drives a long stream of randomly interleaved pushes and pops, timed against heapq. The animation uses a seven-element min-heap, drawn as a tree, and shows one push sifting a small value all the way up to the root, then one pop sifting a value back down — the two motions that are the entire structure.

Build it, one function at a time

Push appends at the next leaf and sifts up until the heap property holds:

def push(self, value, probe=None):
    """O(log n): append the value at the end (the next open leaf), then SIFT UP —
    while it's smaller than its parent, swap them — until the heap order (parent ≤
    children) is restored. It bubbles up at most the height of the tree, log n."""
    a = self._a
    a.append(value)
    i = len(a) - 1
    while i > 0:
        parent = (i - 1) // 2
        if a[parent] <= a[i]:
            break
        a[parent], a[i] = a[i], a[parent]
        i = parent
        if probe is not None:
            probe.append({"arr": list(a), "active": i})
    if probe is not None and not a[:i]:
        probe.append({"arr": list(a), "active": i})

Pop returns the root, moves the last leaf up, and sifts it down past its smaller child:

def pop(self, probe=None):
    """O(log n): the minimum is always at the root, index 0. Return it, move the
    last element into the root, then SIFT DOWN — swap it with its smaller child
    repeatedly — until heap order holds again over the shrunk heap."""
    a = self._a
    if not a:
        raise IndexError("pop from empty heap")
    top = a[0]
    last = a.pop()
    if a:
        a[0] = last
        i, n = 0, len(a)
        while True:
            left, right, smallest = 2 * i + 1, 2 * i + 2, i
            if left < n and a[left] < a[smallest]:
                smallest = left
            if right < n and a[right] < a[smallest]:
                smallest = right
            if smallest == i:
                break
            a[i], a[smallest] = a[smallest], a[i]
            i = smallest
            if probe is not None:
                probe.append({"arr": list(a), "active": i})
    return top

Watch it work

Here's a min-heap drawn as a tree — every parent smaller than its children, the minimum (2) at the root. Watch two operations. First a push of 1: it lands at the bottom as a new leaf, then sifts up, swapping with each parent it's smaller than (orange marks the travelling value), climbing all the way to become the new root. Then a pop: the root leaves, the last leaf moves up to fill it, and it sifts down, swapping with its smaller child until it settles. Two paths, each the height of the tree — that's the O(log n). Notice the heap is never fully sorted; it only ever keeps each parent below its children, which is all it needs:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our MinHeap with sift-up and sift-down. The library tab is heapq, the C binary heap you'd actually use — a set of functions (heappush, heappop, heapify) over a plain list rather than a class.

"""The binary heap — the priority queue. It gives up the search tree's full ordering
for a much weaker one, "every parent beats its children," and in exchange makes one
operation as fast as possible: always hand back the smallest (or largest) element, and
keep doing so as items come and go, all in O(log n).

You already met its trick in heapsort: a complete binary tree flattened into an array,
where node i's children live at 2i+1 and 2i+2, so it needs no pointers. Here it stands
on its own as the structure behind Dijkstra, Huffman coding, event simulation, and every
"process the highest-priority thing next" system.
"""


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

    # region: push
    def push(self, value, probe=None):
        """O(log n): append the value at the end (the next open leaf), then SIFT UP —
        while it's smaller than its parent, swap them — until the heap order (parent ≤
        children) is restored. It bubbles up at most the height of the tree, log n."""
        a = self._a
        a.append(value)
        i = len(a) - 1
        while i > 0:
            parent = (i - 1) // 2
            if a[parent] <= a[i]:
                break
            a[parent], a[i] = a[i], a[parent]
            i = parent
            if probe is not None:
                probe.append({"arr": list(a), "active": i})
        if probe is not None and not a[:i]:
            probe.append({"arr": list(a), "active": i})
    # endregion

    # region: pop
    def pop(self, probe=None):
        """O(log n): the minimum is always at the root, index 0. Return it, move the
        last element into the root, then SIFT DOWN — swap it with its smaller child
        repeatedly — until heap order holds again over the shrunk heap."""
        a = self._a
        if not a:
            raise IndexError("pop from empty heap")
        top = a[0]
        last = a.pop()
        if a:
            a[0] = last
            i, n = 0, len(a)
            while True:
                left, right, smallest = 2 * i + 1, 2 * i + 2, i
                if left < n and a[left] < a[smallest]:
                    smallest = left
                if right < n and a[right] < a[smallest]:
                    smallest = right
                if smallest == i:
                    break
                a[i], a[smallest] = a[smallest], a[i]
                i = smallest
                if probe is not None:
                    probe.append({"arr": list(a), "active": i})
        return top
    # endregion

    def peek(self):
        """O(1): the minimum is always the root — the heap's whole reason to exist."""
        if not self._a:
            raise IndexError("peek at empty heap")
        return self._a[0]

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

    def as_list(self):
        return list(self._a)

"""Python's `heapq` is a binary min-heap over a plain list — exactly this structure, in
C. It's a module of functions rather than a class (`heappush`, `heappop`, `heapify`),
operating on a list you own. It's the priority queue you actually use, and the standard
way to answer "smallest/largest so far" and to run Dijkstra and friends.

The face-off is our MinHeap against `heapq` on the same stream of push/pop operations.
"""
import heapq


# region: heapq_ops
def run_ops_heapq(ops):
    """Drive ('push', x) / ('pop',) on a heapq-managed list."""
    h = []
    out = []
    for op in ops:
        if op[0] == "push":
            heapq.heappush(h, op[1])
        else:
            out.append(heapq.heappop(h))
    return out
# endregion

Scratch vs library

Our MinHeap and heapq are the same structure with the same O(log n) operations, so the gap is the usual constant — about 13× on 400000 operations, Python objects and method calls against C over a raw list. You'd use heapq, always. The value of building it is that the priority queue stops being a black box: when Dijkstra pushes (distance, node) tuples and pops the closest, you now know it's sifting along one path of a packed array; when you see heapq.nlargest, you know it's keeping a small heap; and when someone asks why you can't efficiently change an item's priority mid-heap, you know it's because the heap only tracks parent-child order and would have to search to find the item. The structure is simple; its consequences run through half the algorithms ahead.

Where you'll actually meet it

The heap is the priority queue behind a huge amount of infrastructure. Dijkstra's and Prim's algorithms (graph chapters ahead) use one to always expand the nearest node — it's the difference between those algorithms being fast and being quadratic. Huffman coding builds an optimal compression tree by repeatedly merging the two least-frequent symbols from a heap. Operating-system schedulers and discrete-event simulators pop the next event by time. The nlargest/nsmallest and "top-k trending" queries you see everywhere are size-k heaps. Merging k sorted files or streams — the external-sort step from the merge-sort chapter — uses a heap of stream fronts. Any time a system says "handle the most urgent thing next," a binary heap is very likely underneath.

Takeaways

A binary heap is a complete binary tree packed into an array with the rule "every parent beats its children," giving $O(1)$ access to the extreme and $O(\log n)$ push and pop via sift-up and sift-down. Its partial ordering is deliberately weak — just enough to keep the minimum at the root — which is why it's the cheapest possible structure for the one question it answers and useless for every other. It's the priority queue, heapq in Python, and the engine of the greedy graph algorithms ahead.

The tree tier now turns from these general-purpose ordered structures to specialized trees, each shaped for one kind of data or query. The next chapter, the trie, is a tree keyed not by whole values but by the characters of strings — sharing common prefixes down shared branches — which makes it the structure behind autocomplete, spell-checkers, and IP routing.