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:

    “Our civilization is characterized by the word “progress.” Progress is its form rather than making progress being one of its features. Typically it constructs. It is occupied with building an ever more complicated structure. And even clarity is sought only as a means to this end, not as an end in itself. For me on the contrary clarity, perspicuity are valuable in themselves.”
    —Ludwig Wittgenstein (1889–1951)

    “Whoever places his trust into a system will soon be without a home. While you are building your third story, the two lower ones have already been dismantled.”
    —Franz Grillparzer (1791–1872)

    “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)