Binary heap

Building a heap (Heapify)

Building a heap from an array of n input elements can be done by starting with an empty heap, then successively inserting each element. Equivalently, the heap may be constructed by first arbitrarily placing the elements into the binary tree, then up-heapifying each node successively, which allows in-place heapification. This approach, called Williams' method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.

However, Williams' method is suboptimal. A faster method (due to Floyd) starts by arbitrarily putting the elements on a binary tree, respecting the shape property (the tree could be represented by an array, see below). Then starting from the lowest level and moving upwards, sift the root of each subtree downward as in the deletion algorithm until the heap property is restored. More specifically if all the subtrees starting at some height ${\displaystyle h}$ have already been "heapified" (the bottommost level corresponding to ${\displaystyle h=0}$), the trees at height ${\displaystyle h+1}$ can be heapified by sending their root down along the path of maximum valued children when building a max-heap, or minimum valued children when building a min-heap. This process takes ${\displaystyle O(h)}$ operations (swaps) per node. In this method most of the heapification takes place in the lower levels. Since the height of the heap is ${\displaystyle \lfloor \log n\rfloor }$, the number of nodes at height ${\displaystyle h}$ is ${\displaystyle \le \frac{2^{\lfloor \log n\rfloor }}{2^h}\le \frac{n}{2^h}}$. Therefore, the cost of heapifying all subtrees is:

${\displaystyle \begin{array}{cc}\sum _{h=0}^{\lfloor \log n\rfloor }\frac{n}{2^h}O(h)& =O\left(n\sum _{h=0}^{\lfloor \log n\rfloor }\frac{h}{2^h}\right)\\ & =O\left(n\sum _{h=0}^{\mathrm{\infty }}\frac{h}{2^h}\right)\\ & =O(n)\end{array}}$

This uses the fact that the given infinite series $\sum _{i=0}^{\mathrm{\infty }}i/2^i$ converges.

The exact value of the above (the worst-case number of comparisons during the heap construction) is known to be equal to:

${\displaystyle 2n-2s_2(n)-e_2(n)}$,

where s₂(n) is the sum of all digits of the binary representation of n and e₂(n) is the exponent of 2 in the prime factorization of n.

The average case is more complex to analyze, but it can be shown to asymptotically approach 1.8814 n − 2 log₂n + O(1) comparisons.

The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify (down-heapify for a max-heap) in a bottom-up manner. The array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1)—thus each is a one-element heap, and does not need to be down-heapified. Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.

<b id="mwAUg">Build-Max-Heap</b> (<i id="mwAUk">A</i>): <b id="mwAUo">for each</b> index <i id="mwAUs">i</i> <b id="mwAUw">from</b> <i id="mwAU0">floor</i>(<i id="mwAU4">length</i>(<i id="mwAU8">A</i>)/2) <b id="mwAVA">downto</b> 1 <b id="mwAVE">do:</b> <b id="mwAVI">Max-Heapify</b>(<i id="mwAVM">A</i>, <i id="mwAVQ">i</i>)

Heap implementation

Heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices. These properties make this heap implementation a simple example of an implicit data structure or Ahnentafel list. Details depend on the root position, which in turn may depend on constraints of a programming language used for implementation, or programmer preference. Specifically, sometimes the root is placed at index 1, in order to simplify arithmetic.

Let n be the number of elements in the heap and i be an arbitrary valid index of the array storing the heap. If the tree root is at index 0, with valid indices 0 through n − 1, then each element a at index i has

• children at indices 2i + 1 and 2i + 2
• its parent at index floor((i − 1) / 2).

Therefore, the leaf nodes have indices greater than n / 2. Alternatively, if the tree root is at index 1, with valid indices 1 through n, then each element a at index i has

• children at indices 2i and 2i +1
• its parent at index floor(i / 2).

The leaf nodes then have indices greater than n / 2 + 1.

This implementation is used in the heapsort algorithm which reuses the space allocated to the input array to store the heap (i.e. the algorithm is done in-place). This implementation is also useful as a Priority queue. When a dynamic array is used, insertion of an unbounded number of items is possible.

The upheap or downheap operations can then be stated in terms of an array as follows: suppose that the heap property holds for the indices b, b+1, ..., e. The sift-down function extends the heap property to b−1, b, b+1, ..., e. Only index i = b−1 can violate the heap property. Let j be the index of the largest child of a[i] (for a max-heap, or the smallest child for a min-heap) within the range b, ..., e. (If no such index exists because 2i > e then the heap property holds for the newly extended range and nothing needs to be done.) By swapping the values a[i] and a[j] the heap property for position i is established. At this point, the only problem is that the heap property might not hold for index j. The sift-down function is applied tail-recursively to index j until the heap property is established for all elements.

The sift-down function is fast. In each step it only needs two comparisons and one swap. The index value where it is working doubles in each iteration, so that at most log₂ e steps are required.

For big heaps and using virtual memory, storing elements in an array according to the above scheme is inefficient: (almost) every level is in a different page. B-heaps are binary heaps that keep subtrees in a single page, reducing the number of pages accessed by up to a factor of ten.

The operation of merging two binary heaps takes Θ(n) for equal-sized heaps. The best you can do is (in case of array implementation) simply concatenating the two heap arrays and build a heap of the result. A heap on n elements can be merged with a heap on k elements using O(log n log k) key comparisons, or, in case of a pointer-based implementation, in O(log n log k) time. An algorithm for splitting a heap on n elements into two heaps on k and n-k elements, respectively, based on a new view of heaps as an ordered collections of subheaps was presented in. The algorithm requires O(log n * log n) comparisons. The view also presents a new and conceptually simple algorithm for merging heaps. When merging is a common task, a different heap implementation is recommended, such as binomial heaps, which can be merged in O(log n).

Additionally, a binary heap can be implemented with a traditional binary tree data structure, but there is an issue with finding the adjacent element on the last level on the binary heap when adding an element. This element can be determined algorithmically or by adding extra data to the nodes, called "threading" the tree—instead of merely storing references to the children, we store the inorder successor of the node as well.

It is possible to modify the heap structure to make the extraction of both the smallest and largest element possible in ${\displaystyle O}$${\displaystyle (\log n)}$ time. To do this, the rows alternate between min heap and max-heap. The algorithms are roughly the same, but, in each step, one must consider the alternating rows with alternating comparisons. The performance is roughly the same as a normal single direction heap. This idea can be generalized to a min-max-median heap.

Derivation of index equations

In an array-based heap, the children and parent of a node can be located via simple arithmetic on the node's index. This section derives the relevant equations for heaps with their root at index 0, with additional notes on heaps with their root at index 1.

To avoid confusion, we define the level of a node as its distance from the root, such that the root itself occupies level 0.

Child nodes

For a general node located at index i (beginning from 0), we will first derive the index of its right child, ${\displaystyle \text{right}=2i+2}$.

Let node i be located in level L, and note that any level l contains exactly ${\displaystyle 2^l}$ nodes. Furthermore, there are exactly ${\displaystyle 2^{l+1}-1}$ nodes contained in the layers up to and including layer l (think of binary arithmetic; 0111...111 = 1000...000 - 1). Because the root is stored at 0, the kth node will be stored at index ${\displaystyle (k-1)}$. Putting these observations together yields the following expression for the index of the last node in layer l.

${\displaystyle \text{last}(l)=(2^{l+1}-1)-1=2^{l+1}-2}$

Let there be j nodes after node i in layer L, such that

${\displaystyle \begin{array}{rl}i=& \text{last}(L)-j\\ =& (2^{L+1}-2)-j\end{array}}$

Each of these j nodes must have exactly 2 children, so there must be ${\displaystyle 2j}$ nodes separating i's right child from the end of its layer (${\displaystyle L+1}$).

${\displaystyle \begin{array}{rl}\text{right}=& \text{last(L + 1)}-2j\\ =& (2^{L+2}-2)-2j\\ =& 2(2^{L+1}-2-j)+2\\ =& 2i+2\end{array}}$

Noting that the left child of any node is always 1 place before its right child, we get ${\displaystyle \text{left}=2i+1}$.

If the root is located at index 1 instead of 0, the last node in each level is instead at index ${\displaystyle 2^{l+1}-1}$. Using this throughout yields ${\displaystyle \text{left}=2i}$ and ${\displaystyle \text{right}=2i+1}$ for heaps with their root at 1.

Parent node

Every non-root node is either the left or right child of its parent, so one of the following must hold:

• ${\displaystyle i=2\times (\text{parent})+1}$
• ${\displaystyle i=2\times (\text{parent})+2}$

Hence,

${\displaystyle \text{parent}=\frac{i-1}{2}\text{or}\frac{i-2}{2}}$

Now consider the expression ${\displaystyle \lfloor {\displaystyle \frac{i-1}{2}}\rfloor }$.

If node ${\displaystyle i}$ is a left child, this gives the result immediately, however, it also gives the correct result if node ${\displaystyle i}$ is a right child. In this case, ${\displaystyle (i-2)}$ must be even, and hence ${\displaystyle (i-1)}$ must be odd.

${\displaystyle \begin{array}{rl}\lfloor {\displaystyle \frac{i-1}{2}}\rfloor =& \lfloor {\displaystyle \frac{i-2}{2}}+{\displaystyle \frac{1}{2}}\rfloor \\ =& \frac{i-2}{2}\\ =& \text{parent}\end{array}}$

Therefore, irrespective of whether a node is a left or right child, its parent can be found by the expression:

${\displaystyle \text{parent}=\lfloor {\displaystyle \frac{i-1}{2}}\rfloor }$

Related structures

Since the ordering of siblings in a heap is not specified by the heap property, a single node's two children can be freely interchanged unless doing so violates the shape property (compare with treap). Note, however, that in the common array-based heap, simply swapping the children might also necessitate moving the children's sub-tree nodes to retain the heap property.

The binary heap is a special case of the d-ary heap in which d = 2.

Summary of running times

Here are time complexities of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.