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.
How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$?
data structures
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.