The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
263 views

The minimum number of comparisons required to find the 65th smallest element in a minheap is equal to

asked in DS by Loyal (6.8k points) | 263 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

+5 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 (106k 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? 

0
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 :)

Related questions

0 votes
0 answers
5
asked Dec 6, 2016 in DS by Vishal Goyal Active (1.9k points) | 99 views


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

47,005 questions
51,326 answers
177,509 comments
66,668 users