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 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 Puja Mishra commented Nov 12, 2017 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 .... 0 votes 0 votes vishalshrm539 commented Dec 13, 2017 reply Follow Share 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). 32 votes 32 votes Markzuck commented Nov 19, 2018 reply Follow Share Heapify takes logn or n? As per g4g, it's logn 0 votes 0 votes Swapnil Naik commented Nov 19, 2018 reply Follow Share Heapify() take logn and buildheap() takes O(n) 9 votes 9 votes aditi19 commented Dec 4, 2018 reply Follow Share 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 0 votes 0 votes Shamim Ahmed commented Jan 19, 2019 reply Follow Share The complexity is same as build heap. 0 votes 0 votes Vijay Kusumakar commented Nov 21, 2019 reply Follow Share What is the difference between both the functions? 0 votes 0 votes `JEET commented Nov 21, 2019 reply Follow Share Heapify() and buildheap()? These two you want to know? 0 votes 0 votes `JEET commented Nov 21, 2019 reply Follow Share @Swapnil Naik has explained above. 0 votes 0 votes Nishu Singh commented May 1, 2020 reply Follow Share 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? 0 votes 0 votes Arjun commented May 6, 2020 reply Follow Share No. "Max" or "min" is not the reason for that flexibility -- it is due to "not necessarily one after another" 1 votes 1 votes Prajesh007 commented Aug 22, 2020 reply Follow Share I’m a bit confused . Are we inserting all the n elements in array and then calling build_heap() function? 0 votes 0 votes shashankrustagi commented Dec 8, 2020 reply Follow Share 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) 0 votes 0 votes 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.