Finding the median in a heap

Problem Detail: 

Given a binary heap $H$, indexed in $[1..n]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?

Asked By : Cássio Jandir Pagnoncelli

Answered By : jbapple

It takes $\Omega(n)$ time to find the median of a heap in the worst case. The reason is that the lowest levels of the heap (the leaves and their close ancestors) can be very disordered, and they make up the majority of the heap. As a result, if you can find the median on a heap, you can find a median of the $\Omega(n)$ unordered elements near the leaves. Since finding the median in an unordered list takes $\Omega(n)$ time, so does finding the median in a binary heap.

For instance, if finding the median in an unordered array of size $n$ takes a given amount of time, presumably it shouldn't be any faster to find the median of that array if we prepend to it an array of size $n$ consisting of only $-\infty$ and append to it an array of size $n$ consisting of only $+\infty$. Yet, this new array of size $3n$ is a valid binary heap, and its median is also the median of the original unordered array of size $n$. Thus, if we can find the median of the heap in $O(\log 3n) = O(\log n)$ time, then we can also find the median of an unordered array in $O(\log n)$ time.

Since we know that it takes $\Omega(n)$ time to find the median of an unordered array of size $n$, it must also take $\Omega(n) = \Omega(3n)$ time to find the median of a heap of size $3n$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44587