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, \ldots, n\).
To solve this, we need to determine which nodes are leaves (nodes with no children) and which are internal nodes (nodes with at least one child). A node is a leaf if and only if it has no left child (since in a heap, nodes are filled from left to right, a node cannot have a right child without having a left child).
Node \(i\) has a left child at index \(\textsc{Left}(i) = 2i\). For node \(i\) to have a left child, we need:
\[2i \le n\]Equivalently, node \(i\) is an internal node (has at least one child) if and only if:
\[i \le \lfloor n/2 \rfloor\]This means the internal nodes are exactly those with indices \(1, 2, \ldots, \lfloor n/2 \rfloor\).
By complementarity, the leaves are the nodes with indices greater than \(\lfloor n/2 \rfloor\), which are precisely:
\[\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n\]Let’s verify with an example. Consider a heap with \(n = 10\) elements. We have \(\lfloor 10/2 \rfloor = 5\). The internal nodes are at indices 1 through 5, and the leaves are at indices 6 through 10. Let’s check:
- Node 5: \(\textsc{Left}(5) = 10 \le 10\) ✓ (has a left child, so it’s internal)
- Node 6: \(\textsc{Left}(6) = 12 > 10\) ✓ (no left child, so it’s a leaf)
This confirms our result.