The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
124 views
What is the number of comparisons required to extract 45th element of the min heap?
asked in Algorithms by (197 points) | 124 views
+1
O(1) or$\left ( 2^{45}-1 \right )$

if it is min heap and u r searching from root
0
@srestha please elaborate
0
As here 45 i.e. a constant value is given , comparison will also be constant

right?
0

mam, i hope his ( Rustam Ali ) doubt is, how you say it is ( 245 - 1).

Bye the way did you assume the root height = 1 ?

0

@Shaik

why height will need here?

We only need no of comparison

0

then how you got 245 -1

0
@Shaik

draw this heap tree

1,4,2,5,6,7,3

See the number of comparison to find 3rd minimum is $2^{3}-1$ or not??
0

that is in-directly referring height, when height of root=1

if height of root=0, then it would be 2(h-1) - 1

0
or u can say  level
0
sorry mam, it is level only... by taking height it will create more complexity
0
for height it will be

$2^{h+1}-1$
0
Time complexity will not be O (logn)?????

@srestha
0
0
for the 45th minimumm in heap total uumber of comparisons =sum of first 44 natural numbers=44*45/2=990

Please log in or register to answer this question.

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

47,003 questions
51,323 answers
177,490 comments
66,668 users