Consider a complete binary tree where the left and the right subtrees of the…
2015
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
- A.
\(Ω(log \ 𝑛)\) - B.
\( Ω(𝑛)\) - C.
\(Ω(𝑛 \ log \ 𝑛)\) - D.
\(Ω(𝑛^2)\)
Attempted by 300 students.
Show answer & explanation
Correct answer: A
Answer: Ω(log n).
Reasoning:
The height of a complete binary tree with n nodes is Θ(log n).
Both left and right subtrees are already max-heaps, so the only possible heap-property violation is at the root.
In the worst case the root's element is smaller than every element in the subtrees. To restore the max-heap property the root's element must move down along a root-to-leaf path, requiring at least one swap per level traversed.
That requires at least h = Θ(log n) swaps, so any algorithm needs at least Ω(log n) operations.
A standard percolate-down heapify procedure achieves O(log n) time for this repair, so the Ω(log n) lower bound is tight.
Conclusion: The minimal number of operations required in the worst case is Θ(log n), so the lower bound is Ω(log n).
A video solution is available for this question — log in and enroll to watch it.