Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is , Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Solution

A. Ω (log n)

Explanation

 The answer to this question is simply max-heapify function. Time complexity of max-heapify is O(Log n) as it recourses at most through height of heap.
// A recursive method to heapify a sub tree with root at given index
// this method assumes that the sub trees are already heapified
Void MinHeap::MaxHeapify(int i)
{
Int l = left(i);
Int r = right(i);
Int largest = i;
If (l < heap size && harr[l] < harr[i])
Largest = l;
If (r < heap size && harr[r] < harr[smallest])
Largest = r;
If (largest != i)
{
Swap(&harr[i], &harr[largest]);
MinHeapify(largest);
}
}