The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
4.3k 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)$
asked in DS by (153 points)
edited by | 4.3k views
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).
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 )

4 Answers

+51 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)$.
answered by Veteran (18k points)
edited by
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.
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 .
How 7th smallest element can be in the last level of a min-heap?
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.

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

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

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 .

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.

 

 

 

 

 

 

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})$.
^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)$.
we have to find 7th smallest element. Heap is min heap so 1st smallest is root it self.

for 2nd smallest compare both child of root. whichever is smallest that will be 2nd smallest element.lets say Left child is smaller than right child. so 2nd smallest is Left child of root.

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

for 4th minimum compare left and right child ofjdnd minimum and left and right child of 3rd minimum. total four element. find minimum. declare it as 4th minimum.

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

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

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) 

can you please explain waht 3 check operations will be performed ?
@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
+13 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
answered by Veteran (14.3k points)

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.

@Sachin Mittal. Bro from where did u read this fact? Plz mention the reference :)
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.
answered by (75 points)
–4 votes
The search of 7th smallest element is independent on the input size n so it takes constant time for every input n  O(n)
answered by (223 points)
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.

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

lg(n)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,230 answers
114,269 comments
38,799 users