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:

    “Writing a book I have found to be like building a house. A man forms a plan, and collects materials. He thinks he has enough to raise a large and stately edifice; but after he has arranged, compacted and polished, his work turns out to be a very small performance. The authour however like the builder, knows how much labour his work has cost him; and therefore estimates it at a higher rate than other people think it deserves,”
    —James Boswell (1740–1795)

    “An island always pleases my imagination, even the smallest, as a small continent and integral portion of the globe. I have a fancy for building my hut on one. Even a bare, grassy isle, which I can see entirely over at a glance, has some undefined and mysterious charm for me.”
    —Henry David Thoreau (1817–1862)

    “But generally speaking philistinism presupposes a certain advanced state of civilization where throughout the ages certain traditions have accumulated in a heap and have started to stink.”
    —Vladimir Nabokov (1899–1977)