282 views
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)

Refer https://gateoverflow.in/1110/Gate-cse-2003-question-23 ,this question is similar to the question you have asked.

It’s just O(1) right?
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 ?

### Subscribe to GO Classes for GATE CSE 2022

Let’s assume that all the elements of min heap of n elements are distinct. So, the time required to find the Kth  smallest element in min heap or Kth  largest element in max heap, where K is independent of n will be O(1) as the Kth  smallest element in min heap or Kth  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 5th 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.

by

### 1 comment

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.

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

so it is O(1).

1
134 views