GATE CSE 2003 | Question: 23

Question

In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time

• A. $\Theta (n \log n)$
• B. $\Theta (n)$
• C. $\Theta(\log n)$
• D. $\Theta(1)$

Comments

@SatyamK Heapsort takes $O(n log n)$ time, which is inefficient for this purpose

---

D

---

we are doing asymptotic analysis here and 7^th smallest element will be present within 6^th level(some constant number of nodes will be present) now if we take n as very large number then number of elements we need to compare becomes constant so answer is D.

Answer 1

Time to find the smallest element on a min-heap- one retrieve operation - $\Theta(1)$
Time to find the second smallest element on a min-heap- requires $2^2 - 1 = 3$ check operations to find the second smallest element out of $3$ elements - $\Theta(1)$

Time to find the $7^{th}$ smallest element - requires $O(2^7-1) = O(127)$ check operations to find the seventh smallest element out of $127$ possible ones - $\Theta(1)$

In short if the number of required operations is independent of the input size $n$, then it is always $\Theta(1)$.

(Here, we are doing a level order traversal of the heap and checking the elements)

If we are not allowed to traverse the heap and allowed only default heap-operations, we will be restricted with doing Extract-min $7$ times which would be $O(\log n)$.

Correct Answer: $D$

Comments

duplicates are not allowed, What will be the answer if we were asked to find the

1. $\\ (n-7)^{th} \\ $ smallest element
2. $\\ \frac{n}{7}^{th}\\$ smallest element

 

---

The archive of link provided by @learncp and @Ajay Choudhary 1:

https://web.archive.org/web/20170712171907/http://www.nid.iitkgp.ernet.in/DSamanta/courses/IT60101_2/Archives/Assignment-%20IC%20Binary%20Trees%20Solutions.pdf

---

We are not traversing all n elements, we should traverse up to the 7^th level only to get the 7^th smallest element. We must get the 7^th smallest element between the 7^th level.

As we need to traverse fixed length traversing for any value of n, hence it’s independent from n. That’s why it is O(1).

Answer 2

The 7th most element is always within the 7 levels from the root so we have constant number of nodes in worst condition .we need to check only constant number of nodes to find the 7th smallest number so constant time

Comments

Key point: The k^th smallest element cannot be deeper than the k^th level of the heap, since the path from it to the root must go through elements of decreasing value.

---

@Sachin Mittal. Bro from where did u read this fact? Plz mention the reference :)

---

@Sachin Mittal 1 If input is like 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 2 3 3 4, Now we want to find 3rd smllest then your statement will become False. Please correct me if i am wrong?

 

---

even this is an old thread but i want clarification for concept building

@Sachin Mittal 1 ,  @Digvijay Pandey

since kth smallest element never be beyond to kth level it is true but i think we have to add one more restriction to it, like there are all elements are distinct isn't it ?

---

https://gateoverflow.in/1110/gate2003-23?show=54209#c54209

 

  https://www.interviewbit.com/problems/kth-smallest-element-in-the-array/

---

(k)^th  min element should be between 0^th and (k-1)^th level (both inclusive)

If multiple duplicates exist, then (k)^th min element could be at any level like k, k+1, k+2 etc.

---

because the kth smallest element in a min-heap can be found in [0^th level to k-1 ^th level] which contains the constant number of nodes in this range.

correct me if I'm wrong

Answer 3

The best known algorithm to find Kth smallest element in Min Heap takes - O(K*logK) time and here K = 7th element.

Thus we get O(7*log7) = O(1) as Answer.

Comments

But it required you to maintain a heap of size k itself but in the given question they have mentioned that the heap size is n and not 7.

---

@iarnav the solution you are talking about is using priority queue and it takes 0(klogk) time complexity.

 

Answer 4

3 approaches....
1st- Selection Sort
7 passes to find 7th minimum i.e. 7 × n = O(n)

2nd- Deletion from heap
Deletion of 1 element is logn
Deletion of 7 elements is 7 ×logn = O(logn)

3rd- sum of 1st 6 natural number in heap
O(1)

Among all 3 approaches 3rd one is best so option d is the answer.

Comments

What do you mean by 1^st 6 natural numbers in heap? Can u elaborate?