The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
3.5k 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)$

asked in Algorithms by Veteran (59.5k points) | 3.5k views
0
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??
0
IMO... The remark 'Not necessarily one after another' eliminates this possibility.

5 Answers

+34 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.

answered by Boss (30.8k points)
edited by
0
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 ....
+3
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).
+7 votes
Answer is B.

By build Heap method.
answered by Boss (19.7k points)
0
@ gate keeda can you provide link for how to generate heap using build-heap method
+2
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)$.
+1
@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) ?
0
yes, you are correct. I'll check the question again - because we cannot use $\Theta$ then.
0
Ok Sir.
0
why O(nlogn) just apply build heap on 2n elements. O(2n)= O(n) time
0
@Anirudh That statement should mean that we should do insert whenever one element is available and not wait for all n elements at once.
0
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 .
+4
@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).$
+1
@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.
+3 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
answered by Active (4.4k points)
+2 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)

answered by Loyal (8.4k points)
+2 votes

Hope this video helps : 

answered by Active (1.7k points)
edited by
+1
nice reference ...


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,782 questions
46,784 answers
140,761 comments
58,697 users