The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
6.7k 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 (121 points)
edited by | 6.7k 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
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 )
0
If it is extracted n times and each time it takes logn time, then why not its nlogn
0
@Wanted , It will be $\Theta(1)$..

If you have a min-heap with '$n$' elements then just cut all the elements till 7 levels(i.e. level 0 to level 6 ) of that heap and store it in an another array and build a new min-heap from these elements and find the $7^{th}$ smallest element from it by doing extract-min operations 7 times... Since total elements till $7^{th}$  levels are always constant then both build-heap and extract-min operations will take constant amount of running time on these constant number of elements to get the $7^{th}$ smallest element (with/without repetition)...So, it requires $\Theta(1)$ operations

The best running time to find the $k^{th}$ smallest element in heap is $O(n+k*lgk)$ . We use the same idea for it. We build a heap with $n$ elements .So it requires $O(n)$ time and then cut the elements till $k$ levels of this heap and store it in another array and again create a new heap with these $k$ elements . So  , it takes $O(k)$ time and then apply extract-min '$k$' times. So, it requires $O(k*lgk)$ time. So, Total running time will be $O(n+k+k*lgk)=O(n+k*lgk)$.

But here , In this question , we already have a min-heap structure and $'k'$ is constant here. So, it will take constant amount of time i.e. $\Theta(1)$.
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

5 Answers

+68 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 Boss (18.3k points)
edited by
+8
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.

 

 

 

 

 

 

+8
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})$.
+7
^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)$.
+19
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..

 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) 

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..??
+17 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 Boss (14.4k points)
+22

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?

 

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 (141 points)
0 votes
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.
answered by (209 points)
–3 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 (215 points)
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)
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

44,298 questions
49,785 answers
164,373 comments
65,857 users