11 votes 11 votes What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap? $\Theta(1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$ DS data-structures binary-heap time-complexity + – Vikrant Singh asked Dec 28, 2014 recategorized Jul 6, 2022 by Lakshman Bhaiya Vikrant Singh 3.6k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Anurag_s commented Dec 28, 2014 reply Follow Share It is constant.as long as number is independent of n it can be found with k×k-1/2 Comparisons. 0 votes 0 votes G Shaheena commented Mar 25, 2018 reply Follow Share $\Theta \left ( logn \right )$ 0 votes 0 votes rish1602 commented Aug 13, 2021 reply Follow Share what if they have asked for the upper bound for the number of comparisons? then will it be 0(n) @Anurag_s @Arjun sir 0 votes 0 votes Please log in or register to add a comment.
Best answer 11 votes 11 votes It is constant.as long as number is independent of n it can be found with k×k-1/2 Comparisons. The 50 th smallest element must be within first 50 levels of minheap. for first min :0 comp(root itself) For second min: 0(first min) +1 comp(at level 2) =1For 3 rd min : 0(first min) +1(2 nd min) +2(to compare the child elements of 2nd min and the other node left at 2 nd level : 2 Comparisons for comparing 3 elements to find min )=3SimilarlyFor 50th smalest=0+1+2...+49=49*50/2=1225 Comparisons which is constant We need not delete the elements in which case the complexity will be 50 logn Anurag_s answered Jan 1, 2015 edited Jul 7, 2016 by Anurag_s Anurag_s comment Share Follow See all 10 Comments See all 10 10 Comments reply Arjun commented Jan 1, 2015 reply Follow Share Can you tell the procedure for k = 50? 0 votes 0 votes Anurag_s commented Jan 1, 2015 reply Follow Share The 50 th smallest element must be within first 50 levels of minheap. for first min :0 comp(root itself) For second min: 0(first min) +1 comp(at level 2) =1 For 3 rd min : 0(first min) +1(2 nd min) +2(to compare the child elements of 2nd min and the other node left at 2 nd level : 2 Comparisons for comparing 3 elements to find min )=3 Similarly For 50th smalest=0+1+2...+49= 49*50/2=1225 Comparisons which is constant We need not to delete the elements in which case the complexity will be 50 logn 3 votes 3 votes radha gogia commented Jun 30, 2015 reply Follow Share I have just one confusion that for the root node shouldn't it be that no of comparisons are equal to 1 , while for the second node no of comparisons are 2 since we reached that node after we compared it with the root node and then the node itself ,plz clarify me on the no of comparisons ,little confused that why didn't u consider no of comparsions for root node to be 1 ? 1 votes 1 votes Gate Mm commented Dec 13, 2015 reply Follow Share In level 1,we are comapring the min root wth two elements in the level 1,so isnt it 2 comprisons? @Anurag 0 votes 0 votes khushtak commented Dec 23, 2015 reply Follow Share suppose heap has root=2 left child=4 and right child =6 to find 2nd smallest we need to compare only 4 and 6(only left child with right child) because root is already the smallest element.So only one comparison is needed. 0 votes 0 votes asu commented Jul 30, 2016 reply Follow Share @ arjun sir ,manoj,tauhin i do have finding problem with no of comparision 0 votes 0 votes suraj commented Oct 16, 2016 i edited by suraj Oct 17, 2016 reply Follow Share Nice and well explained answer. But it is not easy to visualize. 0 votes 0 votes srestha commented Nov 4, 2016 reply Follow Share what is n here? if n=50 , then 50 log 50 =300 which is not equal to 1225 Moreover , it is 50 th smallest element where we neednot go upto 50th level for binary heap.right? 0 votes 0 votes Pankaj Joshi commented Jan 23, 2017 reply Follow Share @Anurag while your approach is correct but if we take heap as an abstract data structure then we dont have the traverse operation and we can only do find min and delete min operation and I think that is what is asked in the question hence the answer should be log n 1 votes 1 votes Sunit Kumar commented Jun 5, 2018 reply Follow Share 2(to compare the child elements of 2nd min and the other node left at 2 nd level : 2 Comparisons for comparing 3 elements to find min ) plzz explain it more.. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Deletion of min element from min-heap can be done in logn time. To find the 50th min element we have to perform 49 deletion of min element from the binary min-heap. Therefore, total time to extract 50th min element = 49 lgn = theta(lgn) suraj answered Dec 28, 2014 suraj comment Share Follow See all 2 Comments See all 2 2 Comments reply Shreyans Dhankhar commented Jan 3, 2015 reply Follow Share it is asking for the 50th smallest element then y u r deleting unneccesarily this can easily be performed in constant time i think u will require upto (2^50)-1 checks u will get 50th smallest element 0 votes 0 votes suraj commented Nov 4, 2016 reply Follow Share I understand that it can be done in constant time and my answer is wrong. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Its O(1)http://stackoverflow.com/questions/21600312/searching-the-7th-largest-element-in-a-max-heap Prabhakar9885 answered Mar 13, 2015 Prabhakar9885 comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes If traversal in the min heap allowed then it is constant time or else it is log(n) hungrysoul554 answered Dec 30, 2017 hungrysoul554 comment Share Follow See 1 comment See all 1 1 comment reply ankeshsingh commented Oct 3, 2019 reply Follow Share @Anurag_s Please explain below line: How three comparisons are needed. For 3 rd min : 0(first min) +1(2 nd min) +2(to compare the child elements of 2nd min and the other node left at 2 nd level : 2 Comparisons for comparing 3 elements to find min )=3 0 votes 0 votes Please log in or register to add a comment.