Question

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)$

Comments

It is constant.as long as number is independent of n it can be found with k×k-1/2

Comparisons.

---

$\Theta \left ( logn \right )$

---

what if they have asked for the upper bound for the number of comparisons? then will it be 0(n) 

@Anurag_s   

@Arjun sir

Answer 1

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

Comments

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?

---

@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

---

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..

Answer 2

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)

Comments

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

---

I understand that it can be done in constant time and my answer is wrong.

Answer 3

Its O(1)

http://stackoverflow.com/questions/21600312/searching-the-7th-largest-element-in-a-max-heap

Answer 4

If traversal in the min heap allowed then it is constant time or else it is log(n)

Comments

@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

 

Answer 5

Finding minimum element in a min heap takes O(1) time. To find the 50th smallest element in a min heap needs to delete first 49 smaller elements and then finding the next smaller element, i.e. 50th smallest element. 

Deleting smallest element (root element in a min heap) takes O(logn) time. Total time to delete 49 smaller elements is O(49*logn) = O(logn). Next finding the next min element takes O(1) time. 

Next inserting all the 49 deleted elements need to be inserted back into the heap. That takes O(49*logn). The total time complexity thus becomes O(logn).