# Find the median in a full min-heap with at most $\left \lfloor \frac{n}{2} \right \rfloor$ comparisons

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$$ has no children then return it
2. if $$H$$ has only one child return Select-Var($$H[2...len[H]]$$,$$\left \lfloor \frac{len[H]-1}{2} \right \rfloor$$)
3. if $$H$$ 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.

• There is one child only if the heap has $2$ elements, since the heap is an almost-balanced tree – nir shahar Jun 16 at 9:23
• 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. – Inuyasha Yagami Jun 16 at 17:51
• Can it be that if we have $n=2^k-1$ elements this is an easier case? – oren1 Jun 17 at 10:15