The binary heap is a data structure, in which the keys are store in an array such that each key is guaranteed to be larger than (or equal to) the keys at two other specific positions. In turn, each of those keys must be larger than (or equal to) two additional keys, and so forth (heap-ordered). This ordering is easy to see if we view the keys as being in a binary tree structure with edges from each key to the two keys known to be smaller.

The largest key in a heap-ordered binary tree is found at the root.

Binary heap representation

We draw such a structure by placing the root node and then proceeding down the page and from left to right, drawing and connecting two nodes beneath each node on the previous level until we have draw N nodes. Complete trees provide the opportunity to user a compact array representation that does not involve explicit links. Specifically, we represent complete binary trees sequentially within an array by putting the nodes in level order, with the root at position 1, its children at positions 2 and 3, their children in positions 4, 5, 6, and 7, and so on.

In a binary heap, the parent of the node in position $k$ is in position $k/2$ and, conversely, the two children of the node in positions $2k$ and $2k + 1$. Instead of using explicit links, we can travel up and down by doing simple arithmetic on array indices: to move up the tree from a[k] we set $k$ to $k/2$; to move down the tree we set $k$ to $2 \times k$ or $2 \times k + 1$.

The height of a complete binary tree of size $N$ is $\lg{N}$.

Reheapify

Bottom-up reheapify (swim)

If the heap order is violated because a node’s key becomes larger than that node’s parent’s key, then we can make progress toward fixing the violation by exchanging the node with its parent. After the exchange, the node is larger than both its children, but the node may still be larger than its parent. We can fix that violation in the same way, and so forth, moving up the heap until we reach a node with a larger key, or the root node. Coding this process is straightforward when you keep in mind that the parent of the node at position $k$ in a heap is at position $k/2$.

Insert: we add the new key at the end of the array, increment the size of the binary heap, and then swim up through the heap with that key to restore the heap condition.

Top-down reheapify (sink)

If the heap order is violated because a node’s key becomes smaller than one or both of that node’s children’s keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller (or equal), or the bottom.

Remove the maximum: we take the largest key off the top (root), put the item form the end of the binary heap at the top, decrement the size of the heap, and then sink down through the heap with that key to restore the heap condition.