Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.

A binary heap is a complete binary tree which satisfies the heap property. For a max-heap, this property is:

For every node 𝑖, the value of 𝑖 is greater than or equal to the values of its children.

Formally, if 𝐴A is an array representation of the heap and 𝑖i is a node, then:

𝐴[𝑖]≥𝐴[2𝑖+1] and 𝐴[𝑖]≥𝐴[2𝑖+2]

(assuming a 0-based array indexing).

To prove that the root of any subtree in a max-heap contains the largest value in that subtree, let's consider a node 𝑖 in the max-heap and the subtree rooted at 𝑖.

According to the max-heap property, for the root node 𝑖,

𝐴[𝑖]≥𝐴[2𝑖+1] and 𝐴[𝑖]≥𝐴[2𝑖+2]

This means 𝐴[𝑖] is greater than or equal to its immediate children.

Since the subtree rooted at any child of 𝑖 is also a max-heap, the root of these subtrees will be greater than or equal to all their respective children. Thus, by recursive application of the heap property:

𝐴[2𝑖+1]≥all descendants of 2𝑖+1

𝐴[2𝑖+2]≥all descendants of 2𝑖+2

Thus, A[i]≥all descendants of i

Thus, the root of any subtree in a max-heap contains the largest value occurring anywhere in that subtree.