The Binary Heap

The sorted array keeps the elements in full sorted order, ready to be read off from smallest to largest. But a priority queue never asks for that. It only asks for the single highest-priority element. So far we have tried two extremes, no order at all and total order. What we need is in between: an arrangement that keeps just enough order to know the highest-priority element at all times, without sorting everything else.

That arrangement is a tree. In a short tree, every element is on a path from the root, and the length of that path grows like $\log n$, not $n$. The highest-priority element stays at the root. When add or remove disturbs the order, it only has to fix one path.

This tree is called a binary heap. It is a binary tree that satisfies two properties, and the next two pages define each one. The structure property keeps the tree short: a heap of $n$ nodes has height about $\log n$, the smallest height any binary tree of $n$ nodes can have. We prove this later in the chapter. The order property keeps one of the highest-priority elements at the root. It is the “just enough order” we were looking for, because it compares a node only against its own children. A heap needs both: the order property puts the right element at the root, and the structure property keeps every path short, so restoring the order after a change is cheap.

What does “heap” mean?

The word “heap” means a loose pile of things. The data structure keeps only a little order, with the highest-priority element on top. J. W. J. Williams introduced it in 1964 for the Heapsort algorithm.