Heaps and priority queues: the most urgent first

An emergency department doesn't see patients in the order they arrive. Each one is given an urgency, whoever is most urgent goes next, and new patients keep coming through the door. A queue, from stacks and queues, would hand back whoever has waited longest. This needs a different rule: the item with the highest priority comes out first.

Keep the waiting list sorted and the most urgent is always at one end, but every arrival has to be slotted into place, shifting up to n entries, as in arrays. Keep it unsorted and arrivals are cheap, but finding the most urgent means checking all n. A heap sits in between. It keeps the list only partly in order, just enough that the top item is always first. It is a tree laid out in a plain array with no pointers, and a million entries make a tree just 20 levels deep, so adding or removing one takes at most 19 swaps.

priority queue

The interface: insert an item, peek at the top one, remove the top one. The top is the smallest key or the largest, depending on the queue. A heap is the usual way to build one.

complete binary tree

Every level is full except perhaps the last, which fills from the left. Numbered level by level, its nodes leave no gaps, so they pack into an array.

heap property

In a min-heap every parent is no larger than its children, so the smallest value is at the root. A max-heap flips the rule, and the largest is on top. Either way, no child beats its parent.

index arithmetic

Counting from 0, the children of index i are at 2i + 1 and 2i + 2, and its parent is at ⌊(i − 1) / 2⌋: i − 1 halved and rounded down.

sift up and sift down

How a heap repairs itself after a change: a value swaps with its parent while it beats it (up), or with its better child while that child beats it (down).

This min-heap holds seven values. Read it as a tree, with 2 at the root, or as the strip under it: the array that actually stores the values, with each index below its cell. Each node shows its index too. Insert a value and watch both views change.

Nothing stores where a child is. The tree is complete, so numbering its nodes level by level, left to right, gives exactly the array order, and the children of index i are always at 2i + 1 and 2i + 2. (Some books count from 1, which makes them 2i and 2i + 1 and the parent ⌊i / 2⌋; here, as in Python's heapq, counting starts at 0.)

Notice what the array is not: sorted. It starts as 2, 7, 41, 70, 52, 97, 47, so 70 comes before 52, and 97 before 47. The heap property only compares each parent with its own children. That is enough for a priority queue, because along any path up the tree the values never grow, so the smallest of all sits at the root, index 0, and peeking at it is O(1).

Insert keeps the tree complete first: the new value goes into the next free cell, the end of the array. That may break the heap property with its parent, so it sifts up, swapping with its parent while it is smaller. Each swap climbs one level. Removing the top is the mirror image. Only the last cell can go without leaving a gap, so the last value fills the hole at the root, and then it sifts down.

At each level the sinking value looks at both children and swaps with the smaller one. That child moves up and becomes the parent of its old sibling, so it has to be no larger than the sibling too. The value stops as soon as it is no larger than either child, or when it reaches a leaf.

Completeness is what keeps every path short. A tree allowed to grow lopsided could become a chain of n nodes, and sifting along it would cost O(n). A complete tree has no such chains: each level doubles the room.

This is a max-heap of the same seven values: every parent is no smaller than its children, so 97 sits on top, and a sinking value swaps with its larger child. Insert 80, then extract the root twice. Before each step, predict whether the value swaps with its parent, or which child it swaps with.

A priority queue is what you ask for; a binary heap is how it is usually built. Python's heapq module and Java's PriorityQueue are both binary min-heaps kept in an array. To order tasks by priority in Python, push tuples such as (priority, task), which compare by their first item first. Dijkstra's algorithm keeps its frontier this way, keyed by distance (see the Dijkstra lesson), and so do schedulers, event simulations and "top k" problems.

Here is push for a min-heap kept in a plain list. It appends the value, then climbs: work out the parent's index, stop if the parent is no larger, otherwise swap the two and move up.

def heap_push(heap, x):
    heap.append(x)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent

priorities = [1, 4, 3, 8, 6, 9, 7]
heap_push(priorities, 2)
print(priorities)

The printed list shows how little a heap promises, and that little is what makes it cheap.

Sift down is the step that is easiest to get wrong. A value with two children has a choice to make, one that sift up never faces, since a node has only one parent.

Sometimes all the values arrive at once. Inserting them one at a time costs O(log n) each, O(n log n) in all. Building bottom-up does better. Lay the values out as they are: that is already a complete tree. Every leaf, the second half of the array, is a heap of one. Then walk backwards from the last parent, index ⌊n/2⌋ − 1, to the root, sifting each value down. Both subtrees below it are heaps already, so one sift-down makes its whole subtree a heap.

Four swaps against ten is no accident. Counted the obvious way, though, the build looks no better than inserting: one sift-down per parent, each up to log₂ n levels long.

• A binary heap is a complete binary tree stored in an array counted from 0: the children of i are at 2i + 1 and 2i + 2, its parent at ⌊(i − 1) / 2⌋. No pointers are stored.
• The heap property only compares parents with their children. The top value is at index 0, so peek is O(1), but the array is not sorted, and finding any other value is O(n).
• Insert appends and sifts up; removing the top moves the last value to the root and sifts it down, swapping with the better child. Both walk one path in a tree about log₂ n levels deep: O(log n).
• Building a heap bottom-up from n values is O(n), because most nodes sit near the bottom and barely move.
• A priority queue is the interface (insert, peek, remove the top); a binary heap is the usual implementation.
• Next: heap sort, which builds a max-heap in place and keeps moving the top to the end of the array (the heap sort visualiser), and heaps at work in Dijkstra's algorithm, in Prim's algorithm for minimum spanning trees and in meeting rooms for intervals. Practise with Smash the Heaviest Stones, Kth Largest in a Stream and Kth Largest Number in a List, or open the heap visualiser to try more operations.