Madeeasy Test Series

Question

consider a complete binary tree 'T' with key of root node be 'P'. It is given that the left and right subtree of 'P' satisfies the min-heap property. What is the time taken to convert the given tree 'T' to max-heap?

a. O(log n)

b. O(n)

c. O(nlog n)

d. O(n²)

Answer 1

Let us assume the array representation of min-heap . The approach to do this is :

We simply build Max Heap without caring about the input i.e. we do not care whether the input array is a Minheap or not. We start from bottom-most and rightmost internal mode of min Heap and heapify all internal modes in bottom up way to build the Max heap.

And we know time complexity of building the entire heap takes O(n).So the complexity of given process is O(n) time.Hence B should be the correct answer.

References : http://www.geeksforgeeks.org/convert-min-heap-to-max-heap/

http://www.geeksforgeeks.org/g-fact-85/