Help me implement deleteMax

import java.util.Arrays;/** * * * Use a maximum tree (introduced in Lecture 9) to sort an array. * * To make it simple, I don't use generics here. * It's easy to revise it to use generics. */public class MaxTree { 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; // Build a maximum tree out of an array. public MaxTree(int[] a) { int n = a.length; Node[] nodes = new Node[n]; for (int i = 0; i new Node(a[i]); } while (n > 1) { for (int i = 0; i 2; i++) { int max = Math.max(nodes[i * 2].element, nodes[i * 2 + 1].element); Node newNode = new Node(max); newNode.leftChild = nodes[i * 2]; newNode.rightChild = nodes[i * 2 + 1]; nodes[i] = newNode; // why it's safe to resue the space? } // n might be odd. if (n % 2 != 0) { nodes[n/2] = new Node(nodes[n - 1].element); nodes[n/2].leftChild = nodes[n - 1]; } n = (n + 1) / 2; } root = nodes[0]; } // imlement this // The running time of deleteMax is O( ). public int deleteMax() { return 0; } public static void treeSort(int[] a) { MaxTree tree = new MaxTree(a); for (int i = a.length; i > 0 ; i--) { a[i - 1] = tree.deleteMax(); } } public static void main(String[] args) {// int size = 10;// int[] a = new int[size];// SecureRandom random = new SecureRandom();// for (int i = 0; i // a[i] = random.nextInt(size); int[] a = {3, 2, 6, 13, 8, 4, 10, 7, 14, 11, 12, 5, 9}; System.out.println(Arrays.toString(a)); treeSort(a); System.out.println(Arrays.toString(a)); }}

2. (40 points) In lecture 9, we have introduced how to use a maximum tree to sort an array. It consists of building a maximum tree, and then repeatedly removing the maximum element. The constructor, which builds a maximum tree out of an array, has been provided. Also provided is the treeSort method. Thus, to nish the algorithm, it su'lces to implement the deleteMaJ: metnuu. Your deleteMax met 10d must use 0(log n) time and 0(1) space. 49 3549A 3&35/\\01941949/\\ 1235/\\ /0\\ /19\\ /49 351 101 1949 EEIEIHE