Show that, with the array representation for storing an \(n\)-element heap, the leaves are the nodes indexed by \(\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \dots, n\).

Suppose we have a full tree of depth \(h\). The number of nodes at depth \(h\) (leaf nodes) is \(2^{h-1}\) and the total number of nodes in the tree itself is \(2^{h+1}-1\) (See Exercise 6.1-1 ). There are \(2^{h-1}\) nodes indexed by

\[\begin{equation} \left\lfloor \frac{2^{h+1} - 1}{2} \right\rfloor + 1, \left\lfloor \frac{2^{h+1} - 1}{2} \right\rfloor + 2, \dots, 2^{h+1} - 1 \\ \left\lfloor 2^h + \frac{1}{2} \right\rfloor, \left\lfloor 2^{h} + \frac{3}{2} \right\rfloor, \dots, 2^{h+1} - 1 \\ 2^h, 2^h + 1, \dots, 2^{h+1} - 1 \\ \end{equation}\]

because \(2^{h+1} - 2^{h} = 2^{h-1}\) (which is the above range offset by 1). Thus this claim holds for heaps that are full trees.

Next, consider what happens to a full tree when nodes are added. Adding a new node to a full tree does not change the number of leaves and results in an even value of \(n\), which thanks to flooring our range means the number of referenced elements is unchanged. We have effectively shifted the range by one element such that the new leaf node is included and its parent which is no longer a leaf node is now excluded. Therefore the indexed range still represents all leaves of our heap.

Adding another element will increase the number of leaves by 1 (its parent being the same parent node of our previously added node) and will result in an odd value for \(n\). This conveniently means our range will grow to include an additional element (based once again on the flooring mechanism in the range definition) and so the range still represents all leaves of the heap. From here, adding additional elements oscillates between these two cases: either maintaining the same number of leaves and nodes indexed by this range, or resulting in both the number of leaves and range increasing by 1. In all cases, the range stretches backwards from \(n\) to some midpoint which represents the ‘first’ leaf-node when considering the heap in array form.

Finally, because a single element heap is a full-tree, this argument can be used to construct a heap of any size. Thus this range indeed represents the leaf nodes of any possible heap.