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:

    “Building a conscience is what discipline is all about. The goal is for a youngster to end up believing in decency, and acting—whether anyone is watching or not—in helpful and kind and generous, thoughtful ways.”
    —James L. Hymes, Jr. (20th century)

    “The rage for road building is beneficent for America, where vast distance is so main a consideration in our domestic politics and trade, inasmuch as the great political promise of the invention is to hold the Union staunch, whose days already seem numbered by the mere inconvenience of transporting representatives, judges and officers across such tedious distances of land and water.”
    —Ralph Waldo Emerson (1803–1882)

    “Self-expression is not enough; experiment is not enough; the recording of special moments or cases is not enough. All of the arts have broken faith or lost connection with their origin and function. They have ceased to be concerned with the legitimate and permanent material of art.”
    —Jane Heap (c. 1880–1964)