Question

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0.

If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

• A. O(n)
• B. O(n log n)
• C. O(log n)
• D. O (n loglog n)

Answer 1

The correct option is C O(log n)

Since only root node does not satisfy the heap property, so applying one time heapify will make whole tree as heap. Heapify will take O(log n) i.e. height of heap tree.