# GATE CSE 2003 | Question: 23

19.9k views

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

1. $\Theta (n \log n)$
2. $\Theta (n)$
3. $\Theta(\log n)$
4. $\Theta(1)$
in DS
edited
3
But exact question was "in a heap of size n the 7th smallest element can be found in ?" It is not mentioned anywhere it is min heap or max heap so it should be Θ(n).
4

so just extract root element no do it 7 times

and after each extract take log n so total 7 * log n = O(log n )
0
If it is extracted n times and each time it takes logn time, then why not its nlogn
0

Digvijay Pandey "In a heap with n elements with the smallest element at root"

0
It is given smallest element at the root so it might be minheap
0
Why the complexity is not O(log n).

Because after finding the every smallest element from the min heap we have to heapify the tree too.
0

https://stackoverflow.com/questions/50940998/finding-the-7th-smallest-element-in-min-heap

@Digvijay Pandey  Why cant't we use Heapsort to find time complexity?

0

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

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$

edited
23
If elements are repeated, then also this holds true. Consider the heap array
1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7

The given procedure returns "1" and that is the correct answer. "7" must be returned only if the questions asks "7th" distinct smallest element which might require entire scanning of the heap and needs a hashtable to be run in $O(n)$ time.
3
how will it be constant time? If 7th smallest element is in last level then we need to compare all elements in heap. Then there will be O(n) time required.

If we delete root element (smallest element) and do heapify (requires log n time).

Do it for 7 time to find 7th smallest element. Total time= 7 * log n = log n .
0
How 7th smallest element can be in the last level of a min-heap?
0
7th smallest element can be the largest one in heap.  For example 1 3 9 5 13 11 12 is a list and 13 is 7th smallest element. If we construct heap then 13 will be in last level.
1

It can go only till the 7th level. So, the number of checks is bounded by 2= 127.

2

Why is this  2 -1?

Suppose in a min heap of height 2,we can find the second min in max 2 comparisons.Plz explain anyone

0
5
How is it 3 check operations for finding 2nd minimum element , for finding 1st minimum , we don't require any comparison since we can retrieve it immediately , for retrieving the 2nd minimum element , we require 1 comparison , which is between the two child nodes of the root node and for computing the 3rd minimum we require 2 comparisons since either it will be one among the sibling of 2nd minimum or any child of 2nd minimum element , so likewise series will be formed for finding kth minimum element like

1+2+3+...+k-1=k(k-1)/2 comparisons , although it is also a constant but still value must be considered , so please clarify how u came up with ur logic and what is wrong in logic stated by me .
1

I think ans is o(1), correct but following logic u came up with is wrong. We can find second smallest in only 1 comparision, 3rd smallest requires 2 more comparisions.

20
The answer to this question completely depends on how we phrase out our query. If we were to find the 99th element in a min-heap of 100 elements, it will take $O(1)$. However, if were asked to find the $(n-1)^{th}$ smallest element in that same min-heap, will take $O(\log{n})$.
16
^Well yes, thats how theory is defined. And in your n case, if its added that n is constant (a fixed number), it becomes $O(1)$. The complexity is defined in terms of input- whatever is not part of input can be taken as constant. If $n$ is an input- it becomes $O(\log n)$.
47
we have to find the 7th smallest element. Heap is min heap so smallest is root itself.

For 2nd smallest compare both children of the root. whichever is smallest that will be the 2nd smallest element. Let's say Left child is smaller than the right child so, 2nd smallest is the Left child of the root.

for 3rd smallest compare left and right child of 2nd smallest and sibling of 2nd smallest. total 3 elements. Find the minimum of these three and declare it as 3rd min. let sibling of 2nd min is the smallest so it will be 3rd min.

for 4th minimum compare left and right child 2nd minimum and left and right child of the 3rd minimum. total of four elements. find minimum. declare it as the 4th minimum.

up to the 7th minimum.

complexity = 0 (for minimum no comparison) + 1 (for 2nd min) + 2 (for 3rd minimum) + 3 (for 4th minimum) ..........

= 0+1+2+3.......+6 = 21 comparison. which is constant.

O(1) time only.
0
@Arjun Sir what does it mean by
"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(logn). " in the best answer given above..

0

In order to find the 7 th element one must remove elements one by one from the heap, until the 7 th smallest element is found.
As a heap may contain duplicate values, we may need to remove more then 7 elements. At the worst case we will have to remove
all n elements.
1 deletion takes O(log(n)). Hence ‘n’ deletes will take O(nlog(n)).

0

There is no question 36 or I cannot see Questions after 27.

And see this http://algs4.cs.princeton.edu/24pq/

It says priority queue (which indeed min/max heap ) with duplicate gives any one of largest value for delete_max () operation

So similarly for min heap with duplicate elements it will perform deletemin operation 7 times and each time within logN time it will give minmum element of the min heap. LogN will be taken for heapify.

Taking into consideration what you said then there should be a method to compare previously deleted element with newly deleted element to be sure that both are not identical. And you get truly 7th smallest element (if exists)

0
can you please explain waht 3 check operations will be performed ?
1
@Arjun Sir

I have a doubt sir if say in our array there is no 7th smallest element say our array contain [1,1,1,1,1,1,1,1,1,1]

now in this case we need to do extract min operation n number of times which would give nlogn time?

Plz Correct me Sir
0
But How do you know it is a binary heap..??
2
according to question it is min-heap so always the smallest among all the elements is in the root after applying heapify.

Now 1st delete the 1st smallest element which will result an exchange of the last element of the heap(here, think as element is stored in an array) with the root, now this element can't stay in the root because of heapify which will bring 2nd smallest elements up in the root.It takes O(logn) time.

this procedure will continue upto deletion of 6th smallest element.after that heapify will bring up the 7th smallest element in the root.Now we can find the 7th smallest element by in the root at O(1) time.

So, total time complexity = 6 * O(logn) + O(1) = O(logn)
0

0

@Digvijay Pandey

since I'm an avg student this is the best explanation that i have found but i think 2^7-1 = 127 will be the all possible possibilities for finding the 7th smallest element in heap.(I'm considering all elements are distinct in heap)

but what if if they give kth smallest element :-

then there will be two cases : k is independent to n i.e. k is constant hence again theta(1).

second k is O(n) then time complexity would be O(logn)

and one more thing since they just asked the "Found element or search it " but what if they ask extract it hence kth smallest element extraction operation will take (if k is O(n) ) will be k*log n or (n logn )

isn't it ?

0

sir, why did you take "if we are allowed to traverse root" as a default case? Shouldn't the default be the extract_min() one since that's the default-allowed-operation for a heap?

I mean, how to know if we're allowed to traverse children in a heap or not?

In worst case, we will not be right? So, shouldn't the extract_min() be the default one?

I'm so confused :(

Edit -

There's $O(k)$ algorithm for finding $k^{th}$ smallest element in a min-heap that uses array representation, which makes option (D) the correct choice.

0

@Arjun $sir$,

In a min-heap with n elements

1)  The $7^{th}$ smallest element can be found in time, if duplicates are allowed: $O(1)$

2)  The $7^{th}$ distinct smallest element can be found in time, If duplicates are allowed: $O(n)$.

Why we are getting $O(n)$ for the second case. Please do clarify.

1

@Kushagra गुप्ता In the second case if 122345 is in the heap and they want to know 3rd distinct smallest element then it will be 3 not 2. Similarly in worst case heap can be 1222223, in this case to find 3rd smallest element you have to traverse whole heap.

0

When comparisions are 21 then what is 127?The number of positions we come across? @Digvijay Pandey

0

Could you please explain how you are getting O(log n ) for (n-1)th element?

By using default heap operations only, we get O(log n), but if we are doing heap traversal then, searching  elements should take O(n) time?

0

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

1
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
41

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

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

@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?

1

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

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 ?

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.
0
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.
1 vote
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.
0

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

The question is quite ambiguous.

If the question means

i) it's a min-heap then answer would be O(1), because at worst case we need to check the roots at depth 7, and as we know asymptotic complexity tells the order of growth of time wrt 'n' or input size, here irrespective of n, if it's greater than 7 we only need to check at depth 7 at worst case as I said, even if n is 10, 100, 1000 and so on. So, it's not depending on 'n'.

ii) it's just a binary tree with the least element at the root of the tree then T would be O(nlogn) because at worst case we need to search the entire tree.

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

ago
0

@rish1602

We have to find the 7th smallest element.

Heap is min heap so smallest is root itself.

For 2nd smallest compare both children of the root. whichever is smallest that will be the 2nd smallest element.

Let's say Left child is smaller than the right child so, 2nd smallest is the Left child of the root. for 3rd smallest compare left and right child of 2nd smallest and sibling of 2nd smallest. total 3 elements.

Find the minimum of these three and declare it as 3rd min.

let sibling of 2nd min is the smallest so it will be 3rd min.

for 4th minimum compare left and right child 2nd minimum and left and right child of the 3rd minimum.

total of four elements.

## O(1) time only....

The search of 7th smallest element is independent on the input size n so it takes constant time for every input n  O(n)
0
As heap is minheap already indicating the question as smallest element at the root so to find the 7th smallest from that minheap it will take O(1)  i.e. theta(1) time so (d) is correct.
0

if question is about to find nth smallest element then it will be O(n)???????

1
lg(n)

## Related questions

1
8.5k views
Consider the function $f$ defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL)|| ((p->data <= p ->next -> data) && f(p->next))); } For a given linked list ... in non-decreasing order of data value the elements in the list are sorted in non-increasing order of data value not all elements in the list have the same data value
Let S be a stack of size $n \geq1$. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform $n$ pop operations. Assume that Push and Pop operations take $X$ seconds each, and $Y$ seconds elapse between the end of one such stack operation and the ... $n(X+Y)$ $3Y+2X$ $n(X+Y)-X$ $Y+2X$
A data structure is required for storing a set of integers such that each of the following operations can be done in $O(\log n)$ time, where $n$ is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already ... tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced search tree nor heap can be used