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

The definition of the $7^{\text{th}}$ minimum means that there are at least $7$ elements present.

We know that for the $k^{\text{th}}$ minimum element, the level where it is present lies in the range
from level $0$ to level $(k-1)$.

Therefore, for the $7^{\text{th}}$ minimum, we must traverse levels $0$ to $6$. Hence, the total number
of elements traversed is

\[
\underbrace{2^{0} + 2^{1} + 2^{2} + \cdots + 2^{6}}_{\text{Total traversal}}
 = \left( 2^{7} - 1 \right) = 127.
\]

Thus, the time complexity is

\[
\Theta(127) = \Theta(1).
\]
 

---

why not $log_2(n)$?

if $log_2(n)$ comes into your mind, implies you where thinking just perform extract_min() operation 7 times

well doing this changes the min heap, the goal was to just find the 7th smallest element

for instance, to view the 7th element of a stack, you don't pop() 7 times and then print

---

panipuri

So it's like a fixed fact that for a min heap, the kth element cannot be beyond k-1 th level....So however large the min heap is, we always know the number of levels we need to search(constant) if asked for kth min...Am I correct?

 

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

If we're doing level-order traversal, then for 1st min 0 comparisons, for 2nd min only 1 comparison as it's a min heap and we know root is 1st min, so while traversing we can compare only level 1 elements == 1 comparison.

Let me know if there's an issue in my understanding

 

---

Best Explaination by @Digvijay Pandey sir, truly best, and thanks @Gopal6854 for the elaborated ans on that line with diagrams it helped a lot. 😀

---

in question can be *

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

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

$1st$ minimum will always at root of min heap. Hence, $0$ comparisons.

Now $2nd$ minimum can be child left child or right child of the root. Hence, $1$ comparison.

For the $3rd$ minimum we are assuming that $2nd$ min is the left child of root. So the $3rd$ minimum must be in the childs of $2nd$ min or right child of $1st$ min(root). Because if $3rd$ min is found other places than these nodes then min heap property will be violated (try yourself by some examples). So total comparison $2$.

Now same way I am assuming the $3rd$ min is the left child of the $2nd$ min so the $4th$ min can be found in the the area in the picture below. So to find $4th$ min we have to compare $4$ nodes means $3$ comparisons.

You can try the remaining yourself.

$1st \text{ min} \rightarrow \, 0 \text{ comparison}$

$2nd \text{ min} \rightarrow \, 1 \text{ comparison}$

$3rd \text{ min} \rightarrow \, 2 \text{ comparisons}$

$4th \text{ min} \rightarrow \, 3 \text{ comparisons}$

$5th \text{ min} \rightarrow \, 4 \text{ comparisons}$

$........................$

$........................$

$kth \text{ min} \rightarrow \, (k-1) \text{ comparisons}$

 

$\therefore$ To finnd $kth$ min we need $k(k-1)/2$ comp.

So to find $7th$ min we need  $7(7-1)/2 = 21$ comp.

So time needed $\Theta(1)$.

Option: D 

 

Answer 4

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 5

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?

Answer 6

Sine the 7^th smallest element will be from  ciel( a[7/2] )  to a[7]   hence only “k” comparison are required thus 0(1) is the answer