recategorized by
3,609 views
11 votes
11 votes

What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?

  1. $\Theta(1)$
  2. $\Theta (\log n)$
  3. $\Theta (n)$
  4. $\Theta (n \log n)$
recategorized by

5 Answers

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) =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 delete the elements in which case the complexity will be 50 logn

edited by
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)
1 votes
1 votes
If traversal in the min heap allowed then it is constant time or else it is log(n)

Related questions

1 votes
1 votes
1 answer
1
8 votes
8 votes
3 answers
2
Kapil asked Sep 4, 2016
3,884 views
In a min-heap with n elements1). The 7th smallest element can be found in time, if duplicates are allowed ?2). The 7th distinct smallest element can be found in time, I...
1 votes
1 votes
1 answer
4
gmrishikumar asked Dec 1, 2018
2,244 views
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?