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

Running Time Analysis

The BuildHeap method does exactly tex2html_wrap_inline58047 PercolateDown operations. As discussed above, the running time for PercolateDown is tex2html_wrap_inline69366, where tex2html_wrap_inline62143 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_inline59121. If we make the simplifying assumption that the running time for PercolateDown is tex2html_wrap_inline59121 for every value of i, we get that the total running time for BuildHeap is tex2html_wrap_inline59127.

However, tex2html_wrap_inline60041 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_inline65309 nodes. The sum of the heights of the nodes in T is tex2html_wrap_inline69392.

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_inline69400 nodes at height h-i. Therefore, the sum of the heights of the nodes is tex2html_wrap_inline69404.

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

  eqnarray40770

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

eqnarray40798

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 method is O(n), were n is the length of the array to be heapified.


next up previous contents index

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