Half-sorted is enough

Why can a structure that never fully sorts anything hand you the smallest item instantly?

If you want to know which of a million tasks is most urgent, the obvious move is to sort them and read off the front. It works, and it costs about n log n comparisons — a cost that is not an artefact of a clumsy algorithm but a proven floor, because distinguishing one arrangement of n items from all the others requires at least log2 of n factorial comparisons.

Yet a priority queue hands you the smallest item immediately, and it never sorts anything. Nothing in it is in order. Ask it for the whole sequence and it will happily take its n log n, but ask it only for the front and it answers at once. Where did the sorting go, and what is the structure holding instead?

Start by asking what "sorted" actually commits you to. A sorted sequence answers every comparison question about every pair: for any two items you can say which comes first. That is a total order, and it is an enormous amount of information — roughly n log n bits of it, which is exactly why it costs that much to acquire.

Now ask what the question "which is smallest" actually requires. Only one fact: that some particular item is not larger than any other. Does that require knowing how the other items relate among themselves? Not in the slightest. Those relations are answers to questions you never asked, and you paid for them anyway.

So the design problem becomes: what is the weakest set of relations that still pins down the minimum, and can it be maintained cheaply?

Here is the answer, and it is neat. Arrange the items in a tree, and impose only this: every node is smaller than its children. Nothing else. Siblings are unconstrained. Two items in different branches are unconstrained. The order is partial — it holds along root-to-leaf paths and nowhere else.

Does that give us the minimum? Trace it. Take any item in the tree and walk upward to the root; each step goes to something no larger. So the root is no larger than everything — and that is the entire proof. The minimum is at a known address, readable without any comparison at all.

Now, how much did that cost? Look at how few relations we are asserting: one per edge, so n-1 of them, against roughly n log n for a full sort. The structure is a far weaker commitment, and weaker commitments are cheaper to keep.

Cheaper to keep, though — that is the part to check. What happens on an insertion? Drop the new item at the bottom and compare it with its parent, swapping upward while it is smaller. How far can that go? At most the height of the tree. And here is where the second design choice earns its place: the tree is kept complete, filled level by level, so its height is always about log2 n. No rebalancing rule is needed, because completeness is maintained simply by always adding at the next free slot. Removal is the mirror image — take the root, move the last item into the hole, and sift it down, again at most the height.

One more thing falls out of completeness, and it is easy to miss. A complete tree has no gaps, so it needs no pointers: the children of position i live at 2i+1 and 2i+2 in a plain array. The "tree" is a contiguous block of memory, which is a real practical advantage and not just an implementation detail.

Is there a free lunch here? No, and it is worth being explicit. Extracting all n items one at a time costs n log n, exactly the sorting bound — that is heapsort, and it must be, or we would have beaten a proven lower bound. The win is only there when you want the front and not the rest. Which is the common case: schedulers, event simulations, Dijkstra's frontier, the k smallest of a huge stream.

There is also a pleasant asymmetry. Building a heap from n items already in hand costs only O(n), not O(n log n), because most of the items are near the bottom of the tree and sift down barely at all.

The refinement worth holding on to: the heap is not a partly-finished sort that someone abandoned. It is a complete structure enforcing a different and deliberately weaker invariant. "Half-sorted" is a friendly name for something more precise — a partial order in which comparability holds down ancestor lines and nowhere else.

The misconception to correct follows immediately. People often expect the second-smallest item to be the second element of the array, or expect the heap to be nearly sorted so a final tidy-up would be quick. Neither is true. The second-smallest must be one of the root's two children, so finding it costs a comparison; and beyond that the array order carries no ranking information at all. If you print a heap's array it looks shuffled, because it very nearly is.

One honest boundary: this only pays when the questions you ask match the invariant you maintain. Ask a heap for the largest item, or for a range, or to find an arbitrary key, and it has nothing for you — those are linear scans. A structure that knows less is faster precisely because there is less it can answer.

• Why building a heap from an existing array is linear rather than n log n.
• What a Fibonacci heap buys by making the merge cheap, and why it rarely wins in practice.
• How the same "weakest sufficient invariant" idea shapes quickselect and order statistics.

Every term the collection defines is gathered in the glossary.