54 votes

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

- $\Theta (n \log n)$
- $\Theta (n)$
- $\Theta(\log n)$
- $\Theta(1)$

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

min heap is already created

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 )

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

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.

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

0

Refer this link:

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?

101 votes

Best answer

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$

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$

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.

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 .

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

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.

2

Why is this 2 ^{n }-1?

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

0

@Arjun sir, The given answer in the pdf by IITKGP is O(n*logn). See Q.36 of http://www.nid.iitkgp.ernet.in/DSamanta/courses/IT60101_2/Archives/Assignment-%20IC%20Binary%20Trees%20Solutions.pdf

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+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.

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..

a lot of confusion here.. please help

"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..

a lot of confusion here.. please help

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)).

Ref:Question No.36.http://www.nid.iitkgp.ernet.in/DSamanta/courses/IT60101_2/Archives/Assignment-%20IC%20Binary%20Trees%20Solutions.pdf

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)

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

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

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)

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

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

@Arjun 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.**

Ref: https://gateoverflow.in/66418/7th-smallest-element-in-a-min-heap

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 * n * elements should take O(n) time?

28 votes

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 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.

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

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

4 votes

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.

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

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.

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 votes

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.

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.

0 votes

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

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.