Algorithms: Design and Analysis, Part 1 - Problem Set 5 - Question 5

Problem:

You are given a heap with n elements that supports Insert and Extract-Min. Which of the following tasks can you achieve in $ O(\log(n)) $ time?

Solution 

(Option 1) Find the largest element stored in the heap.
No, the maximum is among the leaf nodes, there are $ O(n) $ leaf nodes and we do not know which one it is.

(Option 2) Find the fifth-smallest element stored in the heap.
Yes, just do delete min 5 times and insert all the other elements back (or alternatively just to a tree traversal of the first 5 levels = 32 nodes, a constant)

(Option 3) Find the median of the elements stored in the heap.

No, it should not be possible. Here is an interesting description of the derivation, latter we will make it precise.

Imagine an infinite heap (there is no bottom to it, yet)

The root has to be the smallest element
The second smallest element has to be in the second layer (2 possibilities)
The third element has to be in the second or third layer (6 possibilities)
The interesting thought is the fourth element, it cannot be in the second layer, and therefore it is in third layer or fourth layer, so (12 possibilities)
...

The key is that, the precise number of possibilities for the median does not matter too much. For a complete binary tree (e.g. 7 nodes, the median will be the fourth), it has at least $ \frac{n}{2} $ possibilities for the median, so if there exist an algorithm to find the median in $ \log(n) $ time, it cannot beat the adversary who place the median somewhere else. (Similar adversary argument can also be applied for option 1)

(Option 4) None of these.
This cannot be true as option 2 is true.