# How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$?

We have a Fibonacci heap with $N$ unique elements we want to make $O(N)$ order statistic queries (e.g., what is the element number 7 in this collection if it was sorted). Moreover, we know that the order statistic queries would be made in order (e.g., for $O(N)$ queries: what is elements number $1,3,5,\ldots,N$) .

How can we do it in $O(N)$ time ? We can't change the data structure in any way.

My thoughts: 1)The naive way is just to do delete min $N$ times but it would take $O(N \log N)$ so its not good enough.

2) if we could somehow use increase-key (if its min heap or decrease-key if its max heap) we would be able do find min in constant time increase its key so its larger than anything else in the heap we could avoid delete-min and its amortized bound of $O(log(n))$ entirely, but we are not allowed to modify the data-structure .

EDIT: sorry i didn't make it clear the heap don't have trees that waiting to be melded , otherwise its not possible since the heap could have N degree 0 trees and we cant sort N items in $O(N)$ time.

• What are your own thoughts on the question? This is not a homework solution service, and we expect you to put most of the effort. – Yuval Filmus Sep 3 '15 at 6:25

Well, you can build a Fibonacci heap in $O(N)$ time. Assuming you will get the proposed order statistic also in $O(N)$ time for the index set $\{1,2,3,\ldots,N\}$, then we can sort the stored set in linear time.
You probably know that (comparision based) sorting takes $\Omega(N \log N)$ time. Since you have no information about the universe of your elements you cannot use tricks like bucket sort or sorting on the word ram to get a linear time sorting algorithm. So you can't solve your problem in $O(N)$ time.
• yea i know. but we don't need to build the heap it's already given to us ... so we cant get a contradiction to comparison based sort because building the heap will take $O(nlogn)$. And if it takes $O(n)$ it means we have n degree 0 trees not melded and a link to min ...... so no contradiction here too because the elements are not sorted , we only know the min element . i'm almost sure its possible . – Boris Morozov Sep 3 '15 at 6:45
• @BorisMorozov, A.Schulz's answer looks to me like a correct answer to your original problem. If there was an algorithm that solves your original problem in $O(N)$ time, it would be possible to sort in $O(N)$ time using only comparisons: simply build a Fibonacci heap (takes $O(N)$ time), then use the hypothetical algorithm. But of course it's not possible to sort in $O(N)$ time using only comparisons. Conclusion: there does not exist an algorithm to solve your original problem in $O(N)$ time using only comparisons. – D.W. Sep 3 '15 at 7:10