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:

    “Little Bill Daggett: I don’t deserve this. To die like this. I was building a house.
    Will Munny: Deserve’s got nothing to do with it.”
    —David Webb Peoples, screenwriter. Little Bill Daggett (Gene Hackman)

    “For we know that if the earthly tent we live in is destroyed, we have a building from God, a house not made with hands, eternal in the heavens.”
    —Bible: New Testament, 2 Corinthians 5:1.

    “Civilisation—a heap of rubble scavenged by scrawny English Lit. vultures.”
    —Malcolm Muggeridge (1903–1990)