Exercise 6.1-3

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

Answer

The base case is trivial since is given by the definition of a max heap. Then we have that for any sub tree of size m so that the index of the root is i. The definition of a max heap can be applied recursively on the child's of i (2i and 2i+1) so by transitivity i most be the largest.