Exercise 6.2-4

What is the effect of calling \(\textsc{Max-Heapify}(A, i)\) for \(i > A.\textit{heap-size}/2\)?

When \(i > A.\textit{heap-size}/2\), the node at index \(i\) is a leaf node. To see why, consider that the left child of node \(i\) would be at index \(2i\). If \(i > A.\textit{heap-size}/2\), then \(2i > A.\textit{heap-size}\), which means the left child index is beyond the heap boundary. Since a node without a left child cannot have a right child either (the heap is filled from left to right), node \(i\) must be a leaf.

Let’s trace through what happens when \(\textsc{Max-Heapify}\) is called on a leaf node:

1. The procedure computes \(l = \textsc{Left}(i) = 2i\) and \(r = \textsc{Right}(i) = 2i + 1\)

2. It checks if \(l \leq A.\textit{heap-size}\). Since \(l = 2i > A.\textit{heap-size}\), this condition is false, so largest is set to \(i\)

3. It checks if \(r \leq A.\textit{heap-size}\). Since \(r = 2i + 1 > A.\textit{heap-size}\), this condition is also false

4. Since largest equals \(i\), the condition largest ≠ i is false, and the procedure terminates without performing any exchanges or recursive calls

The effect is that the procedure does nothing. This makes sense: a leaf node trivially satisfies the max-heap property because it has no children to compare against. The heap property at a leaf is automatically satisfied, so there’s nothing to fix.

The procedure runs in constant time \(\Theta(1)\) for leaf nodes, performing only a few comparisons before terminating.