2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby Jul 21 '15 at 6:18
  • $\begingroup$ Well, I thought $H[\lfloor\frac{n}{2}\rfloor]$ would give the median, but that doesn't seem the correct answer. For instance, $v = [5, 1, 3, 4, 8, 7, 6, 9, 2]$ after heapify becomes $[1, 2, 3, 4, 8, 7, 6, 9, 5]$ whereas median is at the last position. $\endgroup$ – Cássio Jandir Pagnoncelli Jul 21 '15 at 6:55
  • 1
    $\begingroup$ Median, however, seems to reside permanently in the second half of $H$ with no better guess than the brute force $O(n)$ solution. $\endgroup$ – Cássio Jandir Pagnoncelli Jul 21 '15 at 7:00
  • $\begingroup$ $[1,3,2,4,5]$ the median isn't in the second half. $\endgroup$ – François Jul 21 '15 at 13:45
  • $\begingroup$ Agree with "no better than O(n)". $\endgroup$ – WhatsUp Jul 21 '15 at 13:46
6
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

It depends on the structure of your heap. You can create a heap based around the median being the first element, but in a typical min or max heap, it's going to be O(n).

Check this post: https://stackoverflow.com/questions/2579912/how-do-i-find-the-median-of-numbers-in-linear-time-using-heaps

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.