The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
391 views
The minimum number of comparisons required to find the 65th smallest element in a minheap is equal to
asked in DS by Loyal (7.2k points)
edited by | 391 views
0
If they are asking MINIMUM why not 3?
+3
Whenever "minimum" is asked it means "minimum in worst case".
0

 sir for this question minimum and maximum will give the same answer?

1 Answer

+6 votes
Best answer

For $1$st minimum element there is maximum $0$ comparison

For $2$nd minimum element there is maximum $1$ comparison

For $3$rd minimum element there is maximum $2$ comparison

For $4$st minimum element there is maximum $3$ comparison

...............................................................

For $65$st minimum element there is maximum $64$ comparison

So, total number of comparisons $0+1+2+...+64$

                                                     $\frac{64\times 65}{2}=2080$

--------------------------------------------------------------------------------------------------------

Here we operating on min heap and searching for minimum number of comparison. Now, we can compare when atleast $2$ elements in the heap.So, finding minimum element, i.e. at root, we need no comparison

Now, take an example and see for 2nd , 3rd, 4th minimum how many comparison there can be

Now, like this way for $4$ th minimum we need comparison between 4,5,6,8 , So, there must be 3 comparison. Now like this if we go for $5$ th minimum there are 4 comparison

So, there will be total $2080$ comparisons

Note: We just operating like this; When got some minimum, we just add it's child for next comparison and remaining element of previous comparison

Say for $2$ nd minimum, we take child of $1$ st minimum

For $3$ rd minimum , we take remaining element of $2$ nd minimum i.e. $8$ and child of $2$ i.e. $3,6$

answered by Veteran (109k points)
selected by
0
Can you explain how you are calculating comparisons?
0
wht is ans? is ans correct?
+2
+1

They have given the same what you gave. But can you tell how? 

+1
Edited now

plz check it
0
@Arjun Sir

that question is about time required

And this question is "no of comparison"
0

 time and comparisons are proportional to each other

0
but two question is different

right?
0

 yes :)

+1
Beautiful explanation mam !

But if we take Max heap, then in worst case how many number of comparissions for n$^{th}$ smallest element in m keys, is challenging ! isn't it ?
0
Max heap means => keys inserted top to bottom

and finding min means searching bottom to top

then from bottom u need to search upto logn nodes

ok?

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
48,756 questions
52,850 answers
183,548 comments
68,745 users