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

Answer 1

Let the root of the sub-tree be at some position a[i] in the array. From the max-heap property, A[i] >= A[j=2i], if node i has a left-child and A[i] >= A[k=2*i + 1], if node i has a right-sub-tree. But, A[j] >= A[2j], if node j has a left-child and A[j] >= A[2*j + 1], if node j has a right-sub-tree. Likewise, A[k ] >= A[2k+1)], if node k has a left-child and A[k] >= A[2*k +1], if node k has a right-sub-tree. The argument continues for all children in the sub-tree. Hence A[i], the root of the sub-tree, is larger than the value of any child in the sub-tree, so it contains the largest value in the sub-tree