import java.util.ArrayList; public class Heap> { ArrayList heapList; public Heap() { heapList = new ArrayList(); } public int size() { return heapList.size(); } public boolean isEmpty() { return heapList.isEmpty(); } public void clear() { heapList.clear(); } public void enumerate() { System.out.println(heapList); } public void add(T item) { heapList.add(item); int index = heapList.size()-1; int pindex = (index-1)/2; T parent = heapList.get(pindex); while (index>0 && item.compareTo(parent)>0) { heapList.set(index, parent); heapList.set(pindex, item); index = pindex; pindex = (index-1)/2; parent = heapList.get(pindex); } } public T deleteMax() { if (isEmpty()) { System.out.println("Heap is empty"); return null; } else { T ret = heapList.get(0); //get the item in the root. This is the largest item. T item = heapList.remove(heapList.size()-1); //remove the last item. if (heapList.size()==0) return ret; //if there was only one item in the heap to begin with, we are done. heapList.set(0, item); //otherwise, proceed. Put the item in the root. int index, lIndex, rIndex, maxIndex; T maxChild; boolean found=false; index = 0; lIndex = index*2+1; rIndex = index*2+2; while (!found) { if (lIndex0) { maxChild = heapList.get(lIndex); maxIndex = lIndex; } else { maxChild = heapList.get(rIndex); maxIndex = rIndex; } //sift down if necesssary if (item.compareTo(maxChild) 
 
 
 
 
import java.util.Scanner; public class HeapDemo { public static void main(String[] args) { Heap myHeap = new Heap(); Scanner keyboard = new Scanner(System.in); System.out.print("Enter positive integers into the heap (-1 when done): "); Integer num = keyboard.nextInt(); while (num!=-1) { myHeap.add(num); num = keyboard.nextInt(); } System.out.println("The heap: "); myHeap.enumerate(); System.out.print("How many nodes to delete (0 to " + myHeap.size() + ")? "); int d = keyboard.nextInt(); if (dmyHeap.size()) System.out.println("Can't delete"); else if (d==0) myHeap.enumerate(); for(int i=1; i  Part 1: Add the following methods to Heap.java a) Method T findMinO that returns the key with the smallest priority. For instance, if the heap is 90 80 20 70 10 15 5 9 50 the method returns 5. As another example, if the heap is [20, 10, 15, 6, 9, 6], it should return 6. To implement this method, you must not search the entire arraylist. Rather, you should make use of the heap property and do a smart search. [Hint the smallest element is always a leaf node] b) Method T dequeueMin0 that returns the key with the smallest priority and also deletes it. You can modify the sifting up operation to do this. For instance, if the heap is 90 80 60 20 70 10 15 5 9 50 you would first find the smallest priority item using findMinO, then remove the last item (50) and put it in the place of 5 90 80 20 70 10 15 50 9 Next sift 50 up until it finds the right s 90 80 60 50 70 10 15 20 9 If there are muultiple keys with the minimum value, T dequeueMin) just removes one item. Test the two methods in HeapDemo.java. Provide at least three sample outputs