Gate Applied Practice Test

Question

Question--> The time required to find the 99th smallest element from a min heap of n elements is (given that we have access to the array elements)

Comments

Ans depends on many factors.

---

I don’t think so, see if you want to search for the smallest element, the answer is the root. The second smallest element will be present in the next level, The Third Smallest element should be present anywhere between first 3 levels if not, we couldn’t possible push it up for with 3 operations of remove min element of heap. Since, each element of a level can move up a level 1 time for 1 removal op.
So, to find the Nth smallest should reside in Nlevels. Since, N here is a constant you can search if constant time regardless of the size of heap. Note: we don’t use heap operations here, we do a manual search and the search time doesn’t depend on how big the heap is and heap size doesn’t change the max # of elements present at a level.

---

Which IIT you got last year ?

Answer 1

It is O(1) as finding 99 ^th smallest element is finite no of comparison we need . 

so it is O(1).

Answer 2

Let’s assume that all the elements of min heap of n elements are distinct. So, the time required to find the K^th  smallest element in min heap or K^th  largest element in max heap, where K is independent of n will be O(1) as the K^th  smallest element in min heap or K^th  largest element in max heap will be present in the first K-levels (When given that we have access to the array elements)

Let’s say we have a min-heap of 127 elements, so the 5^th smallest element will be present in first 5 levels. So, we need total 1 + 2 + 4 + 8 + 16 comparisons = 31 comparisons = O(1).

So, we need O(1) time.

Comments

Does it really take $31$ comparisons to find the $5^{th}$ smallest element? I believe it’s bound by some constant but I’m not convinced about the $31$ comparisons part... See tournament method for more info, find largest and smallest number takes more than $N$ and below $\frac{3}{2}N$ comparisons surely that's not the case here but I believe it's somewhere in between.