GATE CSE 2015 Set 2 | Question: 17

Question

Consider a complete binary tree where the left and 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. $\Omega(\log n)$
• B. $\Omega(n)$
• C. $\Omega(n \log n)$
• D. $\Omega(n^2)$

Comments

yes.this point is discussed below

---

Catch here is we have a complete binary tree

So this means, this already satisfies the almost complete binary tree property of a max heap

now it is asking best case

$\Omega(logn)$ as this the height of the tree

suppose i have a binary tree

 like

               1

100                    2

To convert this into Max heap, just 1 swap is required.

hence log(n)

---

Sucha good question @GO Classes

Answer 1

Answer is (A).

Here, lower bound imply best algorithm which works for all cases and hence we should consider worst-case.

Max-Heapify(root).

Comments

here, we are given with a tree whose right and left subtree’s are already max heap and this tree is a CBT . so suppose we have the second maximum element at the root ,in this case only constant time is needed to make the tree as a maxheap but if we have the smallest element at the root then we have to do the heapify procedure from top to the leaf. and this will take O(n) right? so if we consider the second case then the time required will be Ω(n)? 

please help in this!

---

Thanks @reena_kandari mam, such a beautiful insight you have given. Problems have various solutions and it’s lower bound tell us the most optimal algorithm in present or future can not do better than this. Where as upper bounds on algorithms tell us how close our solution is to the optimal one.

---

We can think of the question like , we earlier had a max heap . Then we did deleteMax that is we deleted the maximum element . So the right most element from the leaf level came up to take its place . Now we need to again maintain the maxheap property .

Answer 2

now to make it max heap it take only 2 swap and 2 comparision which is nothing but its height.

so logn time needed.

A is asswer

Comments

@Arjun sir if lower bound is worst case input of best algorithm,then what about UPPER BOUND.

isn't lower  bound=best case complexity?

and upper bound=worst case complexity.?

---

@Prashant.

Sir i think here it will take total 4 comparisons and 2 swaps! 

how with only 2 comparisons and 2 swaps we can make this max heap?  as we have to again compare 10 with its respective child nodes!

please help in this!

---

Condition to construct heap is it must be complete binary tree(From left to right)

Answer 3

As to APPLY Heapify(node) to any node its lhs and rhs subtrees must  have to be  HEAP.

Lower bound for heap is its HEIGHT given by log(n)

so it's answer must be A

Answer 4

Go ahead guys with next question without wasting your time. It's a poorly formed question. If this question repeats anywhere you will be able to answer Ω(log n) as it is the smallest. If this question repeats with Ω(1) in option then choose Ω(1) only.

Best Case $\rightarrow$ Ω(1)

Worst Case $\rightarrow$ O(log n)