Prove that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree. Assume a function parent^j (i) (recall functional iteration discussed in section 3.2 of the textbook). You will need to show that A[parent^j (i)] A[i]. Youll do this using mathematical induction on j.

parent^j(i) is defined from functional iteration defined below.

Functional iteration We use the notation f@ (n) to denote the function f(n) iteratively applied i times to an initial value of n. Formally, let f(n) be a function over the reals. For non- negative integers i, we recursively define if i 0 f (i) (n) (n) if i> 0 For example, if f (m) 2n, then f (m) 2in