in Algorithms
30 votes

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

  1. $\Theta(\log n)$

  2. $\Theta(n)$

  3. $\Theta(n\log n)$

  4. $\Theta(n^2)$

in Algorithms


here to insert the first element in the existing  binary heap of n elements time required will be log n, now the second element will be inserted in the heap of n+1 elements so time required will be log n+1 and so on for the nth the total time would be log n + log n+1+ .....+ log n+n and this will be O(nlogn) . plz some one explain i am doing it right or not??
IMO... The remark 'Not necessarily one after another' eliminates this possibility.
Basically we are adding the new n elements to the heap and calling the buidlheap function. which will take O(n) time.

Subscribe to GO Classes for GATE CSE 2022

6 Answers

59 votes
Best answer

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$

edited by


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 .

11 votes
Answer is B.

By build Heap method.


@ gate keeda can you provide link for how to generate heap using build-heap method
it is given in Cormen. Method is simple- do heapify for each element. But analysis is tricky and that proves the complexity as $O(n)$.
@Arjun Sir: What is the significance of the statement: "not necessarily one after another" ? I assumed that this means we can't do the following: append (at once) the n elements in the array representing heap and call Build_Max_Heap method.

If my assumption is correct then shouldn't the correct answer be O(n lg n) ?
yes, you are correct. I'll check the question again - because we cannot use $\Theta$ then.
Ok Sir.
why O(nlogn) just apply build heap on 2n elements. O(2n)= O(n) time
@Anirudh That statement should mean that we should do insert whenever one element is available and not wait for all n elements at once.
sir may be i am not getting correct meaning but "not necessarily one after another" means it is not necessory to insert number one by one . if we have n number then we can insert at a time .
@Anirudh Yes, you are correct. And I checked the original paper- it is $\Theta$ which is also a clue. If we are following one insert after other, complexity would be $O(n \log n)$ but is not $\Theta(n \log n).$
@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.
6 votes
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
5 votes

Hope this video helps : 

edited by

1 comment

nice reference ...
3 votes

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)

1 vote

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.


Related questions