An array of integers of size n can be converted into a heap by adjusting the…
2004
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/ 2⌋, ....., 0. The time required to construct a heap in this manner is
- A.
O(log n)
- B.
O(n)
- C.
O (n log log n)
- D.
O(n log n)
Attempted by 239 students.
Show answer & explanation
Correct answer: B
Answer: O(n)
Reasoning:
Key idea: Sifting down a node costs time proportional to its height (distance from the node to the leaves).
Count of nodes by height: In a complete binary tree, the number of nodes at height h is at most n / 2^{h+1}.
Total work upper bound: Summing the cost over all heights gives
total <= sum_{h>=0} (number of nodes at height h) * O(h) <= n * sum_{h>=0} O(h/2^{h+1}).
The series sum_{h>=0} h/2^{h+1} converges to a constant, so the total is O(n).
Conclusion: The bottom-up heap construction runs in linear time, so the correct time complexity is Θ(n).
Note: This differs from building a heap by inserting elements one at a time into an initially empty heap, which would cost O(n log n).