GATE CSE 2008 | Question: 47

Question

We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is

• A. $\Theta(\log n)$

• B. $\Theta(n)$

• C. $\Theta(n\log n)$

• D. $\Theta(n^2)$

Comments

Basically we are adding the new n elements to the heap and calling the buidlheap function. which will take O(n) time.

---

Right.

---

Right, we are just adding the new 'n' elements to the heap and now we have an array containing '2n' elements out of which only first 'n' elements satisfy the property of heap. So we now have to call build-heap procedure so that the array containing '2n' elements will satisfy the property of heap. This will take $O(2n) = O(n).$

$[Good Question]$

Answer 1

An insert operation on a binary heap takes $\mathcal{O}(\log n)$ time, but an alternative approach we can use. which requires us to insert $n$ elements in heap without any computation i.e. in constant time. after which we can apply Heapify operation(this operation creates heap in linear time) on the array of those element and Hence obtain a Heap in $\mathcal{O}(n)$ time.

---

Here "not necessarily one after another" should mean that we can insert $n$ elements at once and not necesaairly have to wait for first insert to be completed before doing second.

Correct Answer: $B$

Comments

Dont u think it will be nlogn as there will be n build heap calls and heapify takes logn time ??... correct me if i am wrong ....

---

it is O(n), we can take the existing n elements + n new elements= 2n elements and call buildheap , which takes O(n),

so , T.C = O(2n) => O(n).

---

Heapify takes logn or n?

As per g4g, it's logn

---

Heapify() take logn and buildheap() takes O(n)

---

even if we insert all the elements together then call heapify function still won't it take O(logn) time? as heapify takes O(logn) time

---

The complexity is same as build heap.

---

What is the difference between both the functions?

---

Heapify() and buildheap()?

These two you want to know?

---

@Swapnil Naik

has explained above.

---

Can it he said that it is not given that whether it is max or min heap so after inserting each element we don't need to spend logn time to sort and we just have to insert the element on O(1) time for each element and thus for n element it will take O(n) time?

---

No. "Max" or "min" is not the reason for that flexibility -- it is due to "not necessarily one after another"

---

I’m a bit confused . Are we inserting all the n elements in array and then calling build_heap() function?

---

Why did he say that in constant time, we can add?

He should say that we will take linear time to add n ekements

now we have an array of 2n elements

So, buildheap will give O(n)

---

if they give one after other then it will be O(nlogn)?

---

Dont u think it will be nlogn as there will be n build heap calls and heapify takes logn time ??... correct me if i am wrong .…

first a fall see the options they are in $Θ$ notation so you should consider the average case ,the case which you have mentioned is worst case in $nlogn$ time ,but you have the posibility that you can have all elements at once in the existing binary heap ,so this is the average case here ,so to compute the $T.C$ of average case you can first make the binar heap in $O(n)$ time then merge the new binary heap with the priviously existing heap in $O(n+n)$ time so $T.C$ of average case is $Θ(n)$ time .

---

Θ notation so you should consider the average case  ?   is it so

---

No Its not like we have to take average case on Theta notation

---

(Method number according to image given below) In method 1 whenenver we insert element we have to heapify and make it to max heap. But in method 2 we can insert elelment in our own choice so we choose element in such a way that it satisfy max heap we dont have to do heapify.

Now for n element O(n*logn) req with inserting and heapify But with random insertertion n ele insert in O(1) time so O(n) require.

---

heapify means O(logn) or O(n)? i think it is O(logn) is it correct?

EDIT: okay its in comments and my assumption is correct

Answer 2

Answer is B.

By build Heap method.

Comments

@Anirudh: Your statement also makes sense (maybe the question has this meaning itself), I also thought same initially, but when you put all n elements in an array, and start calling build_max_heap method, then it inserts the elements one after another, contradicting the question statement.

Is it a case of poor wording of the question?

@Arjun Sir: Got it sir. Should have taken clue from Theta.

---

but we have insert n element then it must time complexity nlogn

---

Not necessarily @KANCHARLA_AYYAPPA first thing is it given theta instead of O 

Secondly it is given in question we need not insert one after another, so we can append the whole array of given elements to the heap array and do build heap. Build heap is theta n so here it will be theta 2n => theta n only

Answer 3

to insert 1 element into heap it will takes O(logn) time,

so to insert n elements into heap it will take O(nlogn) time.

but there is also a better way means we can apply build heap method for 2n elements it will take O(2n) =O(n).

so b is ans

Answer 4

Hope this video helps : 

Comments

nice reference ...

Answer 5

The worst case time complexity for insertion in a binary heap is O(Logn) (Refer Wiki). So inserting n elements in a heap of size n should take Θ(nlogn) time.
But choice (B) seems to be more appropriate answer. One of the solution of O(n) complexity can be to take the ‘n’ elements of the heap and other ‘n’ elements together and construct heap in O(2n) = O(n)

Answer 6

Answer is (B). 

We can imagine that these first 'n' elements are also not a heap. And then simply add these next 'n' elements at the end of the array. And consder total 2n elements in an array and then call Build Heap(). We know that build heap takes O(n) times. So for these 2n elements it will also takes O(n) times. So is the answer.