In class we implemented a maxheap, with the largest item at the root of the tree. Write the code for the two helper methods that reorganize the heap after an item is added or removed: private void siftUp (int i) private void siftDown (int i) Then compile and run Heaps.java. The output should look like this: original array [8, 5, 3, 9, 2, 7] after converting to a heap [9, 8, 7, 5, 2, 3] removing the largest item [8, 5, 7, 3, 2] removing the largest item [7, 5, 2, 3] adding 13 to the heap [13, 7, 2, 3, 5] adding 1 to the heap [13, 7, 2, 3, 5, 1] after removing everything [ ]

Code

/* * Heap.java * * class for creating a maxheap */ public class Heap> { public static final int DEFAULT_CAPACITY = 10; private T [] collection; private int size; public Heap() { this(DEFAULT_CAPACITY); } @SuppressWarnings("unchecked") public Heap(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("size must be positive!"); } collection = (T []) new Comparable [capacity]; size = 0; } /* * converts an array to a heap */ public Heap(T [] array) { collection = array; size = array.length; int parent = (size-2) / 2; for (int i = parent; i >= 0; i--) { siftDown(i); } } public void add (T item) { ensureSpace(); collection[size] = item; size++; siftUp(size-1); } public T remove () { if (size == 0) { return null; } T removed = collection[0]; collection[0] = collection[size-1]; collection[size-1] = null; size--; siftDown(0); return removed; } public T get() { if (size == 0) { return null; } return collection[0]; } public int size() { return size; } public String toString() { if (size == 0) { return "[ ]"; } String s = "["; for (int i = 0; i < size()-1; i++) { s+= collection[i] + ", "; } return s += collection[size-1] + "]"; } private void ensureSpace() { if (size == collection.length) { @SuppressWarnings("unchecked") T [] larger = (T []) new Comparable [size * 2]; for (int i = 0; i < size; i++) { larger[i] = collection[i]; } collection = larger; larger = null; } } private void siftUp(int i) { // to be implemented } private void siftDown(int i) { // to be implemented } }

**********************************************************************************************************************************************************************************************************************

public class Heaps { public static void main (String [] args) { System.out.println(" creating maxheap (= 'Z' largest) " + "and adding 'A' to it"); Heap letters = new Heap< >(); letters.add('A'); System.out.println(letters); System.out.println(" adding 'Z'"); letters.add('Z'); System.out.println(letters); System.out.println(" adding 'Q'"); letters.add('Q'); System.out.println(letters); System.out.println(" adding 'R'"); letters.add('R'); System.out.println(letters); System.out.println(" removing largest item"); letters.remove(); System.out.println(letters); Integer [] numbers = {8, 5, 3, 9, 2, 7}; System.out.println(" starting with array of integers " + java.util.Arrays.toString(numbers)); Heap h = new Heap< >(numbers); System.out.println(" converting it to a heap " + h); h.remove(); System.out.println(" removing largest item " + h); h.remove(); System.out.println(" removing largest item " + h); h.add(13); System.out.println(" adding 13 " + h); h.add(1); System.out.println(" adding 1 " + h); h.add(4); System.out.println(" adding 4 " + h); h.add(9); System.out.println(" adding 9 " + h); int s = h.size(); for (int i = 0; i < s; i++) { h.remove(); } System.out.println(" after removing everything" + " " + h); } }