Question

Show that the worst-case runtime of the Algorithm Heapify is on an array of length n in Ω(log(n)).
Note: Construct a heap A with n nodes and show that heapify is called recursively accordingly.

Answer 1

Let's say we are performing MAX-HEAPIFY. I am providing the algorithm here.

MAX-HEAPIFY( A, i) //where A is array of length n and i is the index of root

{

l = 2i;

r = 2i+1;

if( l <= A.heap-size && A[ l ] > A[ i ])

largest = l ;

else largest = i;

  if( r <= A.heap-size && A[ r ] > A[ largest ])

largest = r;

if ( largest != i)

exchange A[ i ] with A[ largest]

MAX-HEAPIFY(A, largest); //Recursive call to MAX-HEAPIFY

}

//Building max-heap

BUILD-MAX-HEAP(A)    //where A is array of length n and i is the index of root

{

A.heap_size = A.length

for( i = |_A.length/2_| down to 1)

MAX-HEAPIFY(A, i); //Calling MAX-HEAPIFY FUNCTION

}

Explanation on worst-case runtime of the Algorithm Heapify is on an array of length n in Ω(log(n)).

MAX-HEAPIFY works when a left subtree is heap and also the right subtree is heap but their parent is not following the heap rule.

Now we know that the height of a tree is log(n), where n is the number of nodes.MAX-HEAPIFY, when applied, will result in O(2*logn) which inturn will result in Ω(log(n)). Since 2 is a constant and can be neglected in time-complexity.