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$

Please help me out. Thank you.


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

  • $\begingroup$ How is equality replaced with the greater than equality I cant get that. $\endgroup$ – Sachin Bahukhandi Oct 17 at 4:35
  • $\begingroup$ 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$. $\endgroup$ – aminrd Oct 17 at 4:46
  • $\begingroup$ How is the inequality replaced with equality? $\endgroup$ – Sachin Bahukhandi Nov 26 at 5:46

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.