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 answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments 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 shruti prashar commented Apr 7, 2016 reply Follow Share @ gate keeda can you provide link for how to generate heap using build-heap method 0 votes 0 votes Arjun commented Apr 7, 2016 reply Follow Share 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)$. 6 votes 6 votes Pratyush Madhukar commented Nov 15, 2016 reply Follow Share @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) ? 1 votes 1 votes Arjun commented Nov 15, 2016 reply Follow Share yes, you are correct. I'll check the question again - because we cannot use $\Theta$ then. 0 votes 0 votes Pratyush Madhukar commented Nov 15, 2016 reply Follow Share Ok Sir. 0 votes 0 votes Prashant. commented Nov 15, 2016 reply Follow Share why O(nlogn) just apply build heap on 2n elements. O(2n)= O(n) time 0 votes 0 votes Arjun commented Nov 15, 2016 reply Follow Share @Anirudh That statement should mean that we should do insert whenever one element is available and not wait for all n elements at once. 1 votes 1 votes 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.