1,016 views
1 votes
1 votes
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)

2 Answers

1 votes
1 votes

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

so it is O(1).

1 votes
1 votes

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.

Related questions

1 votes
1 votes
1 answer
1
reena_kandari asked Jul 30, 2016
987 views
The number of elements that can be sorted in time using heap sort ?
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Jun 27, 2019
307 views
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
0 votes
0 votes
0 answers
4