Binary Heap - Building A Heap

Building A Heap

A heap could be built by successive insertions. This approach requires time because each insertion takes time and there are elements. However this is not the optimal method. The optimal method 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, shift 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 (measured from the bottom) have already been "heapified", the trees at height 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 operations (swaps) per node. In this method most of the heapification takes place in the lower levels. Since the height of the heap is, the number of nodes at height is . Therefore, the cost of heapifying all subtrees is:

\begin{align} \sum_{h=0}^{\lceil \lg n \rceil} \frac{n}{2^{h+1}}O(h) & = O\left(n\sum_{h=0}^{\lceil \lg n \rceil} \frac{h}{2^{h + 1}}\right) \\ & \le O\left(n\sum_{h=0}^{\infty} \frac{h}{2^h}\right) \\ & = O(n) \end{align}

This uses the fact that the given infinite series h / 2h converges to 2.


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

,

where s2(n) is the sum of all digits of the binary representation of n and e2(n) is the exponent of 2 in the prime factorization of n.


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 in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree, thus each is a one-element heap. Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.

Build-Max-Heap (A):
heap_length ← length
for i ← floor(length/2) downto 1 do
Max-Heapify(A, i)

Read more about this topic:  Binary Heap

Famous quotes containing the words building a, building and/or heap:

    “History is a child building a sand-castle by the sea, and that child is the whole majesty of man’s power in the world.”
    —Heraclitus (c. 535–475 B.C.)

    “Nowadays almost all man’s improvements, so called, as the building of houses and the cutting down of the forest and of all large trees, simply deform the landscape, and make it more and more tame and cheap.”
    —Henry David Thoreau (1817–1862)

    “A heap of epithets is poor praise: the praise lies in the facts, and in the way of telling them.”
    —Jean De La Bruyère (1645–1696)