Search

0.3.3.2 Analysis

Imagine the distance from a given node down to the most distant leaf node below it is represented by d. In the process of ``heapification,'' the number of comparisons needed to process a given node is, at most, 2d. This is because, in the worst case, when the value at said node is compared to it's two children it will have to be demoted. To determine that the node must be demoted two comparisons are needed: one to compute the greatest child and one to compare the parent node value with the greatest child. Once the values have been swapped it becomes necessary to continue this two-comparison cost process until we reach a leaf node, in the worst case.

Thus the total complexity of the entire ``heapify'' process is, at most, two times the sum of the heights of all nodes in the heap. The goal now is to evaluate this sum.

Consider complete trees (where all nodes have either two children or none). Let H(i) denote the sum of the heights of all nodes a complete tree of height i. A tree of height one has one node with height one. A tree of height i consists of two trees of height (i-1) plus one root node. Hence,

H(i) = 2H(i - 1) + i

Of course H(1) = 1.

The closed form solution of this recurrence relation is:

H(i) = 2ⁱ⁺¹ - (i + 2)

Since a complete binary tree has more nodes than an incomplete one, the total of all node heights in any tree of height i will be less-than or equal to the total node height of the complete binary tree with height i.

Thus the total number of comparisons needed to ``heapify'' a tree of height i will be, at most, O(2(2ⁱ⁺¹ - (i + 2))). This linear complexity can be simplified to O(i) where i is the tree height. Thus, heapification is a linear process.