Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Running Time Analysis

The BuildHeap routine does exactly tex2html_wrap_inline58823 PercolateDown operations. As discussed above, the running time for PercolateDown is tex2html_wrap_inline70367, where tex2html_wrap_inline62992 is the height in the tree of the node at array position i. The highest node in the tree is the root and its height is tex2html_wrap_inline59891. If we make the simplifying assumption that the running time for PercolateDown is tex2html_wrap_inline59891 for every value of i, we get that the total running time for BuildHeap is tex2html_wrap_inline59897.

However, tex2html_wrap_inline60803 is not a tight bound. The maximum number of iterations of the PercolateDown loop done during the entire process of building the heap is equal to the sum of the heights of all of the nodes in the tree! The following theorem shows that this is O(n).

Theorem  Consider a perfect binary tree T of height h having tex2html_wrap_inline66162 nodes. The sum of the heights of the nodes in T is tex2html_wrap_inline70393.

extbfProof A perfect binary tree has 1 node at height h, 2 nodes at height h-1, 4 nodes at height h-2 and so on. In general, there are tex2html_wrap_inline68283 nodes at height h-i. Therefore, the sum of the heights of the nodes is tex2html_wrap_inline70405.

The summation can be solved as follows: First, we make the simple variable substitution i=j-1:

  eqnarray41061

Note that the summation which appears on the right hand side is identical to that on the left. Rearranging Equation gif and simplifying gives:

eqnarray41089

It follows directly from Theorem gif that the sum of the heights of a perfect binary tree is O(n). But a heap is not a perfect tree--it is a complete tree. Nevertheless, it is easy to show that the same bound applies to a complete tree. The proof is left as an exercise for the reader (Exercise gif). Therefore, the running time for the BuildHeap routine is O(n), were n is the length of the array to be heapified.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.