Maintaining the Heap Property

Heapify ( A, i )

Action of the Heapify algorithm

Heapify ( A, i )

1. l ¬ Left ( i )

2. r ¬ Right ( i )

3. if l £ heap-size[A] and A[l] > A[i]

4.        then largest ¬ l

5.        else largest ¬ i

6. if r £ heap-size[A] abd A[r] > A[largest]

7.        then largest ¬ r

8. if largest ¹ i

9.        then exchange A[i] « A[largest]

10.        Heapify ( A, largest)  // so that the heap property is not destroyed

What is the running time of Heapify ( A, i )?

T (n) £ T ( 2/3 n ) + Q  (1) where T ( 2/3 n ) is the cost of fixing the sub tree and Q (1) is the cost of the exchange.

The worst case -- always branch 1 direction.

T (n) = ( lg n )  :: case 2 of the Master Theorem.