SKEDSOFT

We can compute a simple upper bound on the running time of BUILD-MAX-HEAP as follows. Each call to MAX-HEAPIFY costs O(lg n) time, and there are O(n) such calls. Thus, the running time is O(n lg n). This upper bound, though correct, is not asymptotically tight.

We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. Our tighter analysis relies on the properties that an n-element heap has height ⌊lg n⌋  and at most ⌈n/2^{h 1}⌉nodes of any height h.

The time required by MAX-HEAPIFY when called on a node of height h is O(h), so we can express the total cost of BUILD-MAX-HEAP as

The last summation can be evaluated by substituting x = 1/2 in the formula (A.8), which yields

Thus, the running time of BUILD-MAX-HEAP can be bounded as

Hence, we can build a max-heap from an unordered array in linear time.