What is the effect of calling \(\textsc{Max-Heapify}(A, i)\) when the element \(A[i]\) is larger than its children?
When \(A[i]\) is already larger than both of its children, the max-heap property is already satisfied at node \(i\). Let’s trace through what \(\textsc{Max-Heapify}\) does in this case.
The procedure first computes \(l = \textsc{Left}(i)\) and \(r = \textsc{Right}(i)\) to find the indices of the children. Then it compares \(A[i]\) with \(A[l]\) and \(A[r]\) to find the largest among the three values.
Since \(A[i]\) is larger than both children (or the children don’t exist), the variable largest will be set to \(i\). When the procedure reaches line 8, the condition largest ≠ i will be false, so the exchange and recursive call are skipped.
The procedure simply terminates without making any changes to the array.
This is exactly the correct behavior. If the node already satisfies the max-heap property, there’s nothing to fix. The procedure recognizes this situation and terminates immediately in constant time \(\Theta(1)\), avoiding unnecessary work.