241 views
0 votes
0 votes
Consider a complete binary tree where the left and right subtrees of the root are max- heaps. The upper bound of the no. of operations to convert the tree to a heap is:
(a) Ω (log n) (b) Ω (n)
(c) Ω (n log n) (d) Ω (n2)

1 Answer

0 votes
0 votes

Just apply the Max-Heapify procedure on the root. It will convert it into max-heap. It will take order of (log n) time.

Note: To apply the heapfiy procedure on any node. The necessary condition is that both left subtree and right subtree should be max/min heap.

No related questions found