Binary heap

A binary heap represents a priority queue as a complete binary tree obeying a heap order. We use the minimum convention: the priority of every parent in a rooted tree is no greater than the priorities of its children in a rooted tree. Equal priorities are allowed. Each stored entry may be a record carrying a priority key; the numerical example below displays only keys. Reversing the inequalities gives the maximum convention.

The complete binary tree can be stored directly in a zero-indexed array $A=(A_0,\dots ,A_{n-1})$: read its levels from top to bottom, left to right. The root of a tree is at index $0$. The possible children in a rooted tree of index $i$ are at $2i+1$ and $2i+2$, and an index denotes a present entry only when it is less than $n$. For $i>0$, its parent in a rooted tree is at $\lfloor (i-1)/2\rfloor$, using the floor function. Thus the links of the complete binary tree are determined by arithmetic rather than separately stored pointers.

ConsiderThe children in a rooted tree of index $0$ have keys $5,3$; those of index $1$ have keys $9,7$; those of index $2$ have keys $8,4$. The six comparisons $2\le 5$, $2\le 3$, $5\le 9$, $5\le 7$, $3\le 8$, $3\le 4$ establish the heap order. At index $4$, the parent in a rooted tree is index $\lfloor (4-1)/2\rfloor =1$, carrying key $5$.

The array is visibly not a sorted array: $5$ precedes $3$, and $8$ precedes $4$. Nor is the last entry a maximum: it is $4$, whereas the maximum is $9$ at index $3$. The heap order compares ancestors and descendants, without imposing an order between separate branches. Nevertheless, following the graph path from the root of a tree to any entry gives a chain of nondecreasing priorities. This short argument proves that peek can return $A_0$, a minimum, without inspecting the other entries.

Insertion appends an entry to the array, preserving the shape of the complete binary tree, then uses sift up to repair the heap order. Insert key $1$ into the displayed binary heap. It is appended at index $7$, and exchanges with indices $3$, $1$, then $0$:The moving key follows $7\to 3\to 1\to 0$; the keys $9,5,2$ each move down one level. Only this chain needs repair.

Now apply extract-min. Save key $1$, move the last key $9$ to the root of a tree, and shorten the array to length $7$. Use sift down, always choosing the smaller of the present children in a rooted tree:First $9$ exchanges with key $2$ at index $1$, since $2<3$; then with key $5$ at index $3$, since $5<7$. At index $3$, the possible children in a rooted tree would be indices $7,8$, both outside the shortened array, so the process stops. The returned key is $1$, and the remaining binary heap is exactly the original one.

For a nonempty binary heap with $n$ entries, the deepest level is $\lfloor {\log }_{2}n\rfloor$, using the floor function and logarithm. Each exchange moves one level and uses only a bounded number of comparisons. The resulting time complexity bounds, expressed in Big O notation, are:

These bounds assume constant-cost indexed access, key comparisons and exchanges, and available array capacity for insertion. Allocating and copying a larger array is a separate cost. Empty and one-entry cases take constant work.

To build a binary heap, begin at index $\lfloor n/2\rfloor -1$ and work backwards. Entries without children in a rooted tree already obey the heap order. Each sift down, also called heapify down, starts with every present smaller rooted tree below it already repaired. Most entries are close to the bottom and can move very little; successively longer repair distances occur for geometrically fewer entries. Summing these distances gives $O(n)$ work, rather than charging $O(\log n)$ to every entry. MIT's notes give this bottom-up construction and contrast it with repeated insertion.^[ref]

The Dijkstra algorithm additionally needs to decrease the priority of an existing vertex when its tentative distance improves. Given its current index, lowering the key followed by sift up takes $O(\log n)$ time for $n\ge 2$. An indexed binary heap maintains a separate map from item identity to its current index and updates that map after every exchange. For vertices numbered in a fixed range, the map can be another array, giving constant-time index lookup. An ordinary unindexed binary heap supplies no such guarantee: locating an arbitrary item can require scanning $n$ entries. Item identity and priority must remain distinct, especially when several vertices have equal tentative distances.

The attractive compromise is local organization with global usefulness. A binary heap maintains only the heap order, yet every extract-min gives the next smallest key. Repeated extraction of the original example gives $2,3,4,5,7,8,9$, so a priority queue also supplies a sorting algorithm without storing a sorted array between extractions.

In the implementation that exchanges the root with the final leaf and then applies heapify down, a max-heap of size at least four with distinct keys requires at least one downward exchange: the old final leaf's parent remains and has a larger key. One downward exchange can suffice, even for large heaps, by promoting the opposite root child and letting the moved key dominate that child's descendants. Thus the best case is two pairwise exchanges when the initial root/final-leaf exchange is counted. This is a convention about that implementation: a hole-moving implementation uses assignments rather than pairwise exchanges, and the worst case still has logarithmic time complexity.

Construct a binary heap from an array by processing internal nodes backwards, applying sift down at each. The complete binary tree shape ensures that the subtrees below the current node have already been repaired. The number of nodes whose height is at least $h$ is at most $\lfloor n/2^h\rfloor$, so charging each repair by its height gives total work at most a constant multiple of $n+{\sum }_{h\ge 1}\lfloor n/2^h\rfloor <2n$. The construction takes $\Theta (n)$ time in either heap orientation, whereas inserting entries separately has an $O(n\log n)$ worst-case bound.

The minimum convention for heap order requires every parent in a rooted tree to have priority no greater than each of its children in a rooted tree. The displayed formula uses the array representation of a binary heap. It permits equal priorities and does not require a sorted array; the maximum convention reverses the inequality.

After inserting or lowering a key in a minimum-oriented binary heap, compare it with its parent in a rooted tree. Exchange them while the moving key is smaller, then continue at its new index. Stop at the root of a tree or when the heap order is satisfied. This repair assumes the rest of the binary heap was valid before the insertion or key decrease.

To repair a key in a minimum-oriented binary heap, choose the smaller-priority present entry among its children in a rooted tree. Exchange if that entry is smaller than the moving key, and continue at the new index. Stop when there are no children in a rooted tree or the heap order holds. The smaller rooted trees below the starting entry must already obey the heap order; choosing the larger child could leave a violation with the smaller one.