The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
122 views
In a binary Heap of 100 elements time taken to find the 99th element?

or in a binary heap on "n" elements, time taken to find (n-1)th element?

 

Note ; I'm not asking about smallest or largest, but simply the 99th element.
asked in DS by Loyal (9.4k points) | 122 views

1 Answer

+4 votes
Best answer
If you are not asking for 99th smallest or largest element then I assume you are interested in the 99th position of the Array as Heap is nothing but an array with Heap property.

In Array, Direct access to any index is possible, Hence, You can access $n-1$th position of the array in $O(1)$ time.
answered by Boss (21.8k points)
selected by
0
Deepakk if he asked for 99th smallest element, the time taken will still be constant right?
+1
@Lakshay,very obvious case because your input itself is constant.!100 elements only.
0
Ofcourse I know that, but actually I wanted to bring up something else. To find kth smallest, Here in GO they say it will take O($2^k$ - 1) comparisons, but Reddy sir told it will take O(k(k - 1)/2) comparisons. Which one is right?
+1

 if he asked for 99th smallest element, the time taken will still be constant right?

Let's consider for $n$ elements and we are asked to find the $n-1$th smallest which is nothing but $2nd$ largest. ..then time would depend on whether the given heap is max or min....which will be $O(1)$ and $O(n)$ respectively. 

To find kth smallest, Here in GO they say it will take O(2k2k - 1) comparisons, but Reddy sir told it will take O(k(k - 1)/2) comparisons. Which one is right?

 Where did you find (On GO) that To find kth smallest, (2^k - 1) comparisons required. O(k(k - 1)/2) comparisons is correct. 

Which one is right?

Take for instance, K = 1,2,3 etc...And you will find that  k(k - 1)/2 is correct.

0

The GO link to the answer is here https://gateoverflow.in/1110/gate2003-23

I too lean more towards $k(k - 1)/2$, but don't seem to understand why is $2^k - 1$ present as a selected answer there. Yes they want to say that kth smallest element can't go beyond the kth level, but still compared to $k(k - 1)/2$, that's not the tighest bound on number of comparisons.

Related questions

+5 votes
2 answers
3
asked Oct 26, 2016 in Algorithms by jenny101 Active (1.4k points) | 433 views
+2 votes
1 answer
5


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,494 comments
66,668 users