1
$\begingroup$

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?

Edit:

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ There is one child only if the heap has $2$ elements, since the heap is an almost-balanced tree $\endgroup$
    – nir shahar
    Commented Jun 16, 2021 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
    Commented Jun 16, 2021 at 17:51
  • $\begingroup$ Can it be that if we have $n=2^k-1$ elements this is an easier case? $\endgroup$
    – user183748292
    Commented Jun 17, 2021 at 10:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.