Answers · Making it fast enough

How does a heap know the smallest item without keeping the whole collection sorted?

In shortA heap only keeps each parent no larger than its children, so the top is always the smallest even though the rest is not sorted.

A heap knows the smallest item because it keeps one promise: every parent is no larger than either of its children. That forces the root to be the minimum, even though most pairs of items are in no particular order. A valid heap can be [1, 4, 2, 7, 5, 3, 6]. The root is 1, the minimum, but reading across gives 1, 4, 2, 7, 5, 3, 6, which is not sorted: 4 comes before 2 and 5 comes before 3.

The only order it keeps

Positions in a plain array stand for places in a tree. Counting from zero, the item below position $i$ on the left is at $2i+1$ and on the right at $2i+2$ ; the item above is at $\lfloor (i-1)/2 \rfloor$ . The tree has no gaps: every level is full except the last, which fills from the left. That is why no links are stored. From the root, follow any path downwards. Each step goes from a parent to a child, so the value cannot decrease. The root is therefore no larger than every item reachable below it, and every item is reachable below it. The root is the minimum.

\text{children of } i:\; 2i+1 \;\text{ and }\; 2i+2 \qquad \text{parent of } i:\; \left\lfloor \frac{i-1}{2} \right\rfloor

Insertion uses that path in reverse. Start with the heap [1, 4, 2, 7, 5, 3, 6] and add 0. It goes at the end, index 7. Its parent is index $\lfloor(7-1)/2\rfloor=3$ , which holds 7, so the two swap: [1, 4, 2, 0, 5, 3, 6, 7]. The new 0 is now at index 3. Its parent is index $\lfloor(3-1)/2\rfloor=1$ , which holds 4, so swap again: [1, 0, 2, 4, 5, 3, 6, 7]. Its parent is index 0, which holds 1, so swap once more: [0, 1, 2, 4, 5, 3, 6, 7]. Three swaps, and the result is still not sorted, because 5 comes before 3, but every parent is now no larger than its children. At a million items the tree has twenty levels, since $2^{20}=1,048,576$ , so no insertion can need more than twenty swaps.

Removal is the reverse. Take the smallest from [0, 1, 2, 4, 5, 3, 6, 7]. Remove the root 0 and move the last item, 7, into the root position: [7, 1, 2, 4, 5, 3, 6]. The root is now wrong. Compare its children at indices 1 and 2, which hold 1 and 2. The smaller child is 1, so swap 7 with it: [1, 7, 2, 4, 5, 3, 6]. At index 1 the children are at indices 3 and 4, holding 4 and 5. The smaller is 4, so swap: [1, 4, 2, 7, 5, 3, 6]. The root is 1, the new minimum, and the heap property is restored after two swaps. The array is not sorted, but it does not need to be. The briefly wrong top is not a bug in the idea: removal breaks the promise at one place and repairs it by walking one path downwards.

The natural guess

The natural guess is that a priority queue has to keep everything in order. That would work: the smallest is at position 0. The cost appears on insertion. In a sorted block of a million items, putting one new item in the middle shifts about half the block, so 500,000 moves on average. A heap does at most twenty swaps for the same insertion, because it repairs one path rather than the whole array. It also does not maintain the extra order that sortedness gives: it cannot find a named item quickly, and it cannot list a range between two values without inspecting up to all 1,000,000 items. That is the bargain. The only facts needed for repeated minimums are that the root is the minimum and that after each change the root can be repaired along one path.

Where it stops

Where the promise stops being enough is where the question changes. If you need sorted output, a range query, arbitrary deletion, or a search for a particular item, a heap is the wrong structure; it has deliberately thrown that information away. It also gives only the minimum. A maximum needs a separate structure with the comparison reversed, and needing both at once normally means a balanced tree or two heaps. Duplicates are harmless: equal values can sit as parent and child because the promise is no larger, not strictly smaller. The heap is fast only for the one job it promises: repeated removal of the smallest while new items arrive.

Worth keeping

A min-heap guarantees only that every parent is no larger than its children, which is enough to put the minimum at the root.
At a million items the path from root to leaf is about twenty steps, so insertion and removal cost about twenty swaps, while sorted insertion would shift about half a million items on average.
If you need to search for a named item or scan a range, a heap has thrown away the information those questions need.

Where this goes next

This question is one step of Keeping Things in Order, a course that works through its subject from the beginning. The page that teaches this part of it is Always Knowing the Smallest, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course