41 votes 41 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 $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$ Algorithms gatecse-2008 algorithms time-complexity normal + – Kathleen asked Sep 12, 2014 Kathleen 21.8k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply shreshtha5 commented Jun 29, 2015 reply Follow Share 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 votes 0 votes Pranav Kant Gaur commented Jan 7, 2017 reply Follow Share IMO... The remark 'Not necessarily one after another' eliminates this possibility. 0 votes 0 votes Ani_ commented Jan 22, 2018 reply Follow Share https://stackoverflow.com/questions/5057562/how-is-make-heap-in-c-implemented-to-have-complexity-of-3n 0 votes 0 votes susgir2 commented Jan 8, 2019 reply Follow Share Basically we are adding the new n elements to the heap and calling the buidlheap function. which will take O(n) time. 1 votes 1 votes `JEET commented Nov 21, 2019 reply Follow Share Right. 1 votes 1 votes Please log in or register to add a comment.
Best answer 72 votes 72 votes 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$ amarVashishth answered Nov 6, 2015 • edited Apr 29, 2019 by Naveen Kumar 3 amarVashishth comment Share Follow See all 16 Comments See all 16 16 Comments reply Show 13 previous comments Nani909 commented Jan 6, 2021 reply Follow Share if they give one after other then it will be O(nlogn)? 0 votes 0 votes Ritik gupta commented May 10, 2021 reply Follow Share 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 . 0 votes 0 votes Sanjay Sharma commented Oct 13, 2021 reply Follow Share Θ notation so you should consider the average case ? is it so 0 votes 0 votes Please log in or register to add a comment.
12 votes 12 votes Answer is B. By build Heap method. Gate Keeda answered Dec 11, 2014 Gate Keeda comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments Prashant. commented Nov 15, 2016 reply Follow Share 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 . 1 votes 1 votes Arjun commented Nov 15, 2016 reply Follow Share @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).$ 6 votes 6 votes Pratyush Madhukar commented Nov 15, 2016 reply Follow Share @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. 1 votes 1 votes Please log in or register to add a comment.
8 votes 8 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 rajoramanoj answered Aug 19, 2017 rajoramanoj comment Share Follow See all 0 reply Please log in or register to add a comment.
5 votes 5 votes Hope this video helps : Sunny Mukherjee answered Jan 2, 2018 • edited Jan 13, 2018 by Puja Mishra Sunny Mukherjee comment Share Follow See 1 comment See all 1 1 comment reply Puja Mishra commented Jan 11, 2018 reply Follow Share nice reference ... 1 votes 1 votes Please log in or register to add a comment.