2.3k views

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)$

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 element..so 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.

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.

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).

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.

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)

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

Hope this video helps :

edited
nice reference ...