The Gateway to Computer Science Excellence
+9 votes
1.1k views

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)$
in Algorithms by Boss (13.5k points)
edited by | 1.1k views
0
It is constant.as long as number is independent of n it can be found with k×k-1/2

Comparisons.
0
$\Theta \left ( logn \right )$

5 Answers

+11 votes
Best answer

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

by Loyal (8.2k points)
edited by
0
Can you tell the procedure for k = 50?
+3
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
+1
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 ?
0
In level 1,we are comapring the min root wth two elements in the level 1,so isnt it 2 comprisons?

@Anurag
0
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
@ arjun sir ,manoj,tauhin i do have finding problem with no of comparision
0
Nice and well explained answer. But it is not easy to visualize.
0
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?
+1
@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
0
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..
+1 vote
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)
by Loyal (6k points)
0
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
I understand that it can be done in constant time and my answer is wrong.
+1 vote
0 votes
O(1)
by (309 points)
0 votes
If traversal in the min heap allowed then it is constant time or else it is log(n)
by Active (1.4k points)
0

@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

 

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,157 answers
193,767 comments
93,746 users