$1.$ The tree below is introduced in lecture $6$ to demonstrate how to find max $($To find max or the second, we do not need to store the tree. The idea for finding second cannot be used to find the third. Why?$)$

We can build this tree and use it to implement selection sort in a better way.

$$ Implement the constructor, which builds a maximum tree out of an array.

$$ Implement the deleteMax method, which removes the maximum element from the tree.

$$ Implement the treeSort method to use this tree to do selection sort. Hint: please make sure you understand the tree before starting. During the execution, the leaves are precisely the set of unprocessed elements

$!!!$ very IMPORTANT: Do not change anything in Node class!!!

package comp$2011.$a$2$;

import java.util.Arrays;

public class MaxTree$\_23123456$d$\_$GigiYimMingHay $\{//$ Please change!

$/*$

$*$ No modification to the class $\{$@code Node$\}$ is allowed.

$*/$

private class Node $\{$

int element;

public Node leftChild, rightChild;

public Node$($int element$)\{$ this.element $=$ element; $\}$

public String toString$()\{$ return String.valueOf$($element$)$; $\}$

$\}$

Node root;

$/**$

$*$ The constructor: Build a maximum tree out of an array.

$*$

$*$ VERY IMPORTANT.

$*$ I've sought help from the following Internet resources and books:

$*1.$

$*2.$

$*3.$

$*...$

$*$

$*$ Running time: O$().$

$*/$

public MaxTree$\_23123456$d$\_$GigiYimMingHay$($int$[]$ a$)\{$

$\}$

$/*$

$*$ Remove the root from a maximum tree and return its element.

$*/$

$*$ I've sought help from the following Internet resources and books:

$*1.$

$*2.$

$*3.$

$*...$

$*$

$*$ Running time: O$().$

$*/$

public int removeMax$()\{$

$\}$

$/**$

$*$ The $*$smart$*$ selection sort.

$*$

$*$ VERY IMPORTANT.

$*$ I've sought help from the following Internet resources and books:

$*1.$

$*2.$

$*3.$

$*...$

$*$

$*$ Running time: O$()$; space use: O$().$

$*/$

public static void treeSort$($int$[]$ a$)\{$

$\}$

$/*$

$*$ Todo: add at least ten more test cases to test your code.

$*$ The use of data structures from Java libraries is allowed here and only here.

$*/$

public static void main$($String$[]$ args$)\{$

int testData$[][]=\{//$ try different inputs.

$\{\},$

$\{1,1,1,1,1,1,1\},$

$\{10,8,-4,89,2,0,4,-19,200\},$

$\{5,4,3,2,1,1,0,0,-1\},$

$\{1,2,3,4,5,6,7,8,9,10,11\},$

$\{1,3,2,6,7,5,4,12,13,15,14,10,11,9,8\},$

$\{3,2,6,13,8,4,10,7,14,11,12,5,9\},$

$\{65,85,17,88,66,71,45,38,95,48,18,68,60,96,55\},$

$\{10,8,14,89,32,50,77,38\}$

$\}$;

for $($int$[]$ a:testData$)\{$

System.out.println$("$The original array: $"+$ Arrays.toString$($a$))$;

treeSort$($a$)$;

System.out.println$("$Sorted: $"+$ Arrays.toString$($a$))$;

$\}$

$\}$

$\}$