Exercise 6.1-7

Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by :

Answer

We can define that a node at an index i is a leave if and only if

We can check if this definition holds for:

so we have: 

since the rest are greater the result of multiplying them by 2 will also be greater than n