An array X of n distinct integers is interpreted as a complete binary tree.…
2006
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 (log n)
- C.
O (nlog n)
- D.
O (n log log n)
Attempted by 264 students.
Show answer & explanation
Correct answer: B
Answer: O (log n).
Explanation: The array represents a complete binary tree with n nodes. If only the root violates the heap property, restore the heap by performing a sift-down (heapify) starting at the root.
Per-level work: O(1) — compare the node with its children and possibly swap.
Number of levels: O(log n) — height of a complete binary tree.
Total time: O(1) × O(log n) = O(log n).
Note: Building a heap from an arbitrary array by heapifying all nodes takes O(n) overall, and heap sort takes O(n log n). Those are different scenarios and do not change the answer for the single-root-violation case.