**Objective:** The goal of this assignment is to practice the
use of heaps and array implementation of trees.

**Reminder:** In an array representation of a tree, for an
element a[k] stored in the k-th cell, its left child is stored
as a[2k+1] and its right child is stored as a[2k+2]. For example,
a tree

3 / \ 1 5 / \ / \ 0 2 4 6is stored as follows:

3 1 5 0 2 4 6 a[0] a[1] a[2] a[3] a[4] a[5] a[6]In this implementation, to describe a subtree, it is sufficient to describe its root. For example, if we give the index 2 (corresponding to element 5), this describe the following subtree:

5 / \ 4 6For simplicity, let us assume that all elements of the tree are non-negative integers, and -1 means that that there is no element. For example, a tree

3 / \ 1 5 \ / 2 4is stored as follows:

3 1 5 -1 2 4 -1 a[0] a[1] a[2] a[3] a[4] a[5] a[6]

**Assignment:** For the array representation of the trees,
write several recursive methods related to trees:

- a method that, given an array and an index, returns the smallest element of the corresponding subtree;
- a method that, given an array and an index, returns the largest element of the corresponding subtree;
- a method that, given an array and an index, returns the total number of elements in the corresponding subtree;
- a method that, given an array and an index, returns the height of the corresponding subtree;
- a method that, given an element, an array, and an index, checks whether the given element belongs to the corresponding subtree;
- a method that, given an element, an array, and an index, adds the given element to the corresponding subtree.