Most Efficient Way to find the logn th Maximum in a Max Heap

Question

The title says it all; What is the most efficient way to find the log nth maximum number in a max heap with n elements?
ps: The text book I'm reading vaguely explained a solution with time complexity of O(lognloglogn) by using another heap that I can't understand, can we do better than that?

Answer 1

Let H be the original max-heap. Let H' be another max-heap, initially empty, that operates on pairs (index, value) of elements from the first heap and orders the pairs based on the second component.

1. H'.push(0, H[0])
2. count = ceil(log n)
3. while count > 0 do
   4. (i, v) := H'.extract-max() // takes O(log log n) time
   5. H'.push(2i+1, H[2i+1]) if H[2i+1] exists // O(log log n) time
   6. H'.push(2i+1, H[2i+2]) if H[2i+2] exists // O(log log n) time
   7. count := count - 1
4. return v

The reason we have O(log log n) bounds on running times of operations of H' is that H' contains at most log n elements and each operation runs in time logarithmic in the number of elements of the heap, which is O(log log n).

The total running time is obviously O(log n log log n). I'm assuming the original max-heap H is represented with an array.