The Priority Queue

A regular queue serves items in arrival order. Some systems instead need to process the item with the highest priority.

A priority queue maintains this ordering and returns the highest-priority item next.

The core interface has three operations: insert, peek-max, and extract-max. Each concerns the top of the ordering; there is no promise to find the tenth-highest item efficiently.

Keeping the interface narrow is what allows the implementation to stay fast.

The standard implementation is a binary heap, which is a complete binary tree stored in an array. Every level is full except possibly the last, which fills from left to right.

For a node at index i, the parent is at (i-1)/2 and the children are at 2i+1 and 2i+2. No pointers are required.

In a max-heap, every parent is greater than or equal to both of its children.

Siblings are not ordered relative to each other, and an in-order traversal does not produce sorted output. Maintaining this partial order requires less work than maintaining a fully sorted collection.

To insert, append the new value at the first free slot — the next position in the array — preserving completeness. Then sift up: compare the new node against its parent, and if it is larger, swap. Repeat until the parent is larger or the node reaches the root.

Each swap moves the node up one level, so the number of swaps is bounded by the tree's height: O(log n). Nothing else in the tree needs to change.

Extract-max removes the root — the maximum by the heap property — and needs to fill the gap without breaking completeness. The fix: move the last array element into the root position, shrink the array by one, then sift down.

Sifting down compares the out-of-place node against both children and swaps with the larger child (never the smaller — that would violate the heap property immediately), repeating until the node is larger than both children or has none. Again bounded by tree height: O(log n).

Inserting n items individually costs O(n log n). A heap can instead be built from an existing array by applying sift-down from the last internal node back to the root. Leaves require no work because each is already a valid one-node heap.

Most nodes are near the bottom and move only a short distance. Summing the work across all nodes gives O(n) construction time, a result associated with Floyd’s 1964 treesort3.

A binary heap cannot search efficiently for an arbitrary key or iterate through items in sorted order. It provides efficient access only to the highest-priority item.

The array representation requires no pointers or tree rotations. Insert, peek, and extract cost O(log n) or better and generally have good cache locality.

Dijkstra's algorithm needs an operation the plain interface doesn't offer: lower the priority of an item that is already sitting in the queue, because a shorter path to it was just found. A plain binary heap has no way to locate that item without scanning the whole array.

The fix is an indexed heap: keep a side map from key to array position, updated on every swap. Decrease-key then looks up the slot in O(1) and sifts up from there in O(log n). When merging two whole heaps also needs to be cheap, the binary heap gives way to the meldable family — binomial, Fibonacci, and pairing heaps — which trade code complexity for a faster decrease-key and near-constant-time merge.

Dijkstra’s algorithm, A*, and Prim’s algorithm repeatedly select the candidate with the lowest current cost. Event loops use heaps to select the next timer to execute. When priorities are bounded integers and predecessor or successor queries also matter, a van Emde Boas tree provides a different priority-queue design with O(log log U) operations.

Python, C++, and Rust expose heap implementations in their standard libraries. LSM-tree compaction uses a heap to merge sorted runs, and heapsort repeatedly extracts items into an output array.

A binary heap maintains a partial order in which every parent has at least the priority of its children. It supports O(log n) insertion and extraction, O(1) access to the top item, and O(n) construction from an array.

This partial ordering is sufficient for workloads that repeatedly need only the highest- or lowest-priority item.