#DataStructure Heaps Self Doubt.

Question

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.

Answer 1

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.

Comments

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?

---

 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.

---

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.