I'm thinking to do this recursively using the fact the the left subheap is also a min-heap with its root being the minimum using some variation of Select$\left \lfloor \frac{n}{2} \right \rfloor$.

Select-Var($H$,$\left \lfloor \frac{len[H]}{2} \right \rfloor$):

  1. if $H[1]$ has no children then return it
  2. if $H[1]$ has only one child return Select-Var($H[2...len[H]]$,$\left \lfloor \frac{len[H]-1}{2} \right \rfloor$)
  3. if $H[1]$ has two children ...?

How can I complete this algorithm? or is there any better way to do this?


The second part of the above algorithm is redundant because the heap is assumed to be full - a full binary tree with $n=2^k-1$ nodes.

I also found that the median can be at any level of the tree except for the root.

  • $\begingroup$ There is one child only if the heap has $2$ elements, since the heap is an almost-balanced tree $\endgroup$ – nir shahar Jun 16 at 9:23
  • 1
    $\begingroup$ The current best upper bound for finding the median is $2.95 \cdot n$ comparisons. If you could find the median in min heap using $\lfloor n/2 \rfloor$ comparisons, then you can improve on this bound to $2.5 \cdot n$ comparisons since building heap takes at most $2n$ comparisons. $\endgroup$ – Inuyasha Yagami Jun 16 at 17:51
  • $\begingroup$ Can it be that if we have $n=2^k-1$ elements this is an easier case? $\endgroup$ – oren1 Jun 17 at 10:15

Your Answer

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

Browse other questions tagged or ask your own question.