# 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

## 1 Answer

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
• @D.W., I understand the answer the reason i'm asking is i was sure myself its impossible for the same exact reasons. it was a question in exam and i wrote this exact words and my answer was marked as wrong . dunno maybe its a mistake of the grader. – Boris Morozov Sep 3 '15 at 7:50
• @BorisMorozov, in the future, it would be better to have included that information in your question from the start, so people don't waste their time by telling you something you already know. We can't read your mind -- if you don't tell us that's the context/motivation for your question, I don't know how we could possibly tell. Anyway: Have you considered asking your instructor about this question on the exam? – D.W. Sep 3 '15 at 16:49
• @D.W., i will include that information in the future , i wanted to keep things short and simple . I will have a chance to ask him later today . – Boris Morozov Sep 6 '15 at 4:44