A FIFO queue serves jobs in arrival order. That works until one job matters more than its position in line: a fire alarm submitted after a print job still needs to fire before the print job runs.
Arrival order and importance are different orderings, and a FIFO queue only tracks the first. The structure that always serves the most important item next, regardless of when it arrived, is a priority queue.
A priority queue exposes exactly three operations: insert, peek-max, and extract-max. Every one of them is about the top of the ordering — there is no operation to inspect the tenth-highest item, and none is needed.
That narrow interface is the whole point. Restricting what the structure promises is what lets its implementation be fast and simple.
The standard implementation is a binary heap: a complete binary tree — every level full except possibly the last, which fills left to right — stored flat in an array with no pointers at all. Node i's parent lives at index (i-1)/2; its children live at 2i+1 and 2i+2.
Completeness is what makes the array trick work: a complete tree has no gaps, so indexing arithmetic alone locates every relationship. The tree drawing and the array row above are the same seven numbers, viewed two ways.
The only invariant a binary heap maintains is that every parent is greater than or equal to both of its children. Nothing else about the arrangement is constrained.
In particular, siblings carry no ordering relative to each other, and a heap is not a sorted array wearing a tree shape — an in-order walk of a heap does not produce sorted output. The heap property is weaker than full sortedness, and that weakness is exactly what makes it cheap to maintain.
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 one at a time costs O(n log n). But building a heap from an already-full array is faster: run sift-down starting from the last internal node and sweep back to the root, skipping the leaves entirely — they are already valid one-node heaps.
The trick is that most nodes are near the bottom, where sift-down does almost no work; only the few nodes near the root pay for their full height. Summed across all nodes, the total work is O(n), not O(n log n) — a result usually attributed to Floyd's 1964 treesort3.
A binary heap gives up the ability to search for an arbitrary key or scan the collection in any meaningful order. There is no efficient way to ask "is value X in this heap?" — only the maximum is ever cheap to find.
In exchange it needs no pointers, no rebalancing logic, and no allocation beyond a single growable array. Every operation that matters — insert, peek, extract — costs O(log n) or better, with excellent cache locality from the flat array layout.
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 and A* both repeatedly ask "which frontier node is closest so far?" — exactly a peek-max (or peek-min) query. Prim's MST asks the same question of edges. All three are, at their core, a loop around a priority queue.
Event loops and timer wheels use heaps to answer "what fires next?" — libuv's timer implementation is a binary heap, and the Go runtime historically used a 4-ary heap for the same purpose. Standard libraries expose heaps directly: Python's heapq, C++'s std::priority_queue, Rust's BinaryHeap. LSM-tree compaction uses a heap to merge many sorted runs at once (see the LSM Tree chapter) — and heapsort itself is just repeated extract-max into an output array.
An array, plus one invariant: every parent is at least as large as its children. Insert and extract both cost O(log n), at either end of the ordering, and building from scratch costs only O(n).
The heap gives up global order so it can guarantee the one comparison that actually gets asked over and over — what's on top — cheaply. Sorted just enough, and nothing more.