= Binary heap
{wiki}
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,\ldots,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.
Consider
$$
A=(2,5,3,9,7,8,4).
$$
The <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\le5$, $2\le3$, $5\le9$, $5\le7$, $3\le8$, $3\le4$ establish the <heap order>. At index $4$, the <parent in a rooted tree> is index $\lfloor(4-1)/2\rfloor=1$, carrying key $5$.
\Image[/binary-heap-array-and-tree.png]
{title=One <binary heap> viewed as an <array> and a <complete binary tree>}
{description=Matching indices identify the same entries in both representations. The <heap order> compares each <parent in a rooted tree> with its <children in a rooted tree>; it does not make a <sorted array>.}
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$:
$$
\begin{aligned}
(2,5,3,9,7,8,4,1)&\longrightarrow(2,5,3,1,7,8,4,9)\\
&\longrightarrow(2,1,3,5,7,8,4,9)\\
&\longrightarrow(1,2,3,5,7,8,4,9).
\end{aligned}
$$
The moving key follows $7\to3\to1\to0$; 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>:
$$
\begin{aligned}
(9,2,3,5,7,8,4)&\longrightarrow(2,9,3,5,7,8,4)\\
&\longrightarrow(2,5,3,9,7,8,4).
\end{aligned}
$$
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.
\Image[/binary-heap-sift-operations.png]
{title=<Sift up> inserts 1, then <sift down> restores the original <binary heap> after removing 1}
{description=The four panels show the start and end of each repair. Colored arrows mark the moving key's <graph path>. The extraction panels contain seven entries: index 3 has no <children in a rooted tree>.}
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:
|| Operation
|| <Time complexity>
|| Reason
| `peek`
| $O(1)$
| Read the <root of a tree>.
| Insert
| $O(\log n)$ for $n\ge2$
| Append, then <sift up> through at most the levels of the <complete binary tree>.
| `extract-min`
| $O(\log n)$ for $n\ge2$
| Move the last entry, then <sift down> through at most those levels.
| Build from an arbitrary <array>
| $O(n)$
| Apply <sift down> from the last index with <children in a rooted tree> back to index $0$.
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.https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/40d4851e550507ca14dc778b9b2266cc_MIT6_006S20_lec8.pdf[MIT 6.006, lecture 8: implicit indices, heap repair and linear build, pp. 3–6]{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\ge2$. 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.
Back to article page
