GATE IT 2006 | Question: 72

Question

An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

• A. $O (n)$
• B. $O (\log n)$
• C. $O (n \log n)$
• D. $O (n \log \log n)$

Comments

what will be the time complexity if worst case asked in question.. ??

---

If they Ask Worst Case ,so what will be the Time complexity in Worst Case..Anyone Plz Clear my Doubt..

---

Can I say this question is similar to https://gateoverflow.in/8091/gate2015-2-17 ?? One is asking lower bound other is asking best case!!

---

Answer is $\Omega (1)$ and $O(logn)$ Hence, (B) is the correct option.

---

rare event when year 2006 question is that straight forward

Answer 1

Here we need to call Heapify/ Bubble down/ Percolate down procedure on Root, which in the worst case will take time $O (\log n).$ So $B$ is the correct option.

Other options do not even make sense, because with $O(n)$ we can even build an entire Heap not just heapify on the root. $O (n \log n) \;\&\; O (n \log \log n)$ is more than $O(n)$.

Comments

But what if O(1) would hv been in options ..??

---

just think root contains the smallest element among all elements in the heap

Then We have to go either the entire Left Part or the entire Right Part of the whole Tree.

---

@Himanshu1, Omega(1) would've been right not O(1).

---

they ask best asymptotic time complexity ..but options given in Upper bound ...so what we understand from that is...they ask what is upper bound in Best case..i.e we cant go further than in best  case....

so 0(1) not be the answer if they mesion in option ..because it tells we can do at constant time in any best case ..but it is false be cause root can be go till last level also possible ..

if they give omega(1)..it  is correct because in some case we root just go to 1 level down ..

Answer 2

The question is saying best case which will be when only one swap will be required which will be order of $1$.
As no option matches just call heapify at the root - $O(\log n)$.

Comments

@Ayush sir what wiil be the TC in case for worst asymptotic time complexity

---

@Lakshaysaini2013-Worst would be $O(n)$. Consider the the right subtree of root to be a min heap and left subtree to be a max heap. And you finally want a min heap.

---

most valuable answer❤️

Answer 3

Step 1:delete the root and replace it with last element and heapify takes O(log n) Step 2: inserting the deleted element again takes O(log n) time so its O(2log n) and finally O(log n)

Comments

Why not simply call Heapify without an insert or delete?

---

@Arjun: You are correct ,why would we delete the element .

We can just call heapify and it will also take logn time only as other nodes are already in place.

---

what will be the time complexity if worst case asked in question.. ??

---

Worst will be logn

and i think the correct answer should be o(1) for the guven question as it is aksed the best time