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.

## Comments