Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.
The key insight is that the max-heap property applies to every node in the heap, not just the overall root. Let’s think about what this means for any arbitrary subtree.
Consider any node \(i\) in the heap. We want to show that the value at node \(i\) is greater than or equal to all values in the subtree rooted at \(i\).
By the max-heap property, for every node \(j\) (other than the root of the entire heap), we have:
\[A[\textsc{Parent}(j)] \ge A[j]\]This means each node’s value is at most its parent’s value. Now consider any node \(k\) in the subtree rooted at \(i\). To reach node \(k\) from node \(i\) in the tree, we must traverse down some path from \(i\) to \(k\). At each step along this path, we move from a parent to a child, and the max-heap property guarantees that the parent’s value is at least as large as the child’s value.
Therefore, following the path from \(i\) down to \(k\), the values are non-increasing. This means:
\[A[i] \ge A[k]\]Since this holds for any node \(k\) in the subtree rooted at \(i\), we conclude that \(A[i]\) is the largest value in that subtree.