7.8k 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)$
edited | 7.8k views
+2
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

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

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

+1

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

+9
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})$.
+8
^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)$.
+25
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..??
0
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

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

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.

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

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

1
2