2 votes 2 votes Consider a complete binary tree where the left and the right sub trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is: $\Omega(\log n)$ $\Omega(n\log n)$ $\Omega(n)$ $\Omega(n^2)$ DS nielit2017dec-scientistb data-structures binary-tree binary-heap + – admin asked Mar 30, 2020 • retagged Oct 28, 2020 by Krithiga2101 admin 1.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply Ollie commented Jun 15, 2020 reply Follow Share https://gateoverflow.in/8091/gate2015-2-17 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Simply call Max_Heapify() on the root. A single heapify call will cause the root to percolate down the tree and the maximum height of a complete binary tree is log n. Therefore, the lower bound for the number of operations to convert the tree to a heap is Ω(logn). AkashChandraGupta answered Aug 6, 2020 AkashChandraGupta comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The answer to this question is simply max-heapify function on root (Max-Heapify(root)). Time complexity of max-heapify is $\omega(Log n)$ as it recurses at most through height of heap. Mohit Kumar 6 answered May 31, 2020 Mohit Kumar 6 comment Share Follow See 1 comment See all 1 1 comment reply gatecse commented Aug 1, 2020 reply Follow Share When you say "at most" you'll get upper bound - big-O. For lower bound it must be "at least". 2 votes 2 votes Please log in or register to add a comment.