# Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n

The Question of the CLRS $$6.1-7$$ exercise reads as:

Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by $$\lfloor n / 2 \rfloor + 1, \lfloor n / 2 \rfloor + 2, \ldots, n⌊n/2⌋+1,⌊n/2⌋+2,…,n$$.

I looked for the solution here: https://walkccc.github.io/CLRS/Chap06/6.1/

The solution was provided like this:

Let's take the left child of the node indexed by $$\lfloor n / 2 \rfloor + 1.$$

\begin{aligned} \text{LEFT}(\lfloor n / 2 \rfloor + 1) & = 2(\lfloor n / 2 \rfloor + 1) \\ & > 2(n / 2 - 1) + 2 \\ & = n - 2 + 2 \\ & = n. \end{aligned}

I can't understand this statement: $$LEFT(⌊𝑛/2⌋+1) > 2(𝑛/2−1)+2$$

So, basically in heap representation, $$LEFT(i)$$ refers to the index of $$i's$$ left child. What we want to show is that index $$⌊𝑛/2⌋+1$$ is a leaf and is not a middleware node which can be proved if we could show the index of the left child is larger than the number of elements in the heap.
On the other hand, $$LEFT(⌊𝑛/2⌋+1) = 2(⌊𝑛/2⌋+1) = 2⌊𝑛/2⌋+2$$ and with removing those brackets around the $$n/2$$ we can show that it is larger than $$2(n/2-1)+2 = n$$.
• Because we know that for all $n$ we have $n-1 < ⌊𝑛⌋ \leq n$. So $n/2-1 < ⌊𝑛/2⌋ \leq n/2$ and $2(𝑛/2−1)+2 < 2⌊𝑛/2⌋+2$. – aminrd Oct 17 '19 at 4:46