Need Help in Java!!

In this homework assignment, you will be building and testing a Min Heap. A min heap is a complete binary tree where the minimum-valued element is stored at the root node and where every node is less than or equal two both of its child nodes.Your assignment will be to build and test the following classes:

MinHeapInterface

MinHeap

MinHeapTest

You can use the corresponding max classes as examples to follow. However, your classes should (of course) create a min heap instead of a max heap. You should create your classes in the heap package.

Problem 1 (5 points): Create the MinHeapInterface interface. Make sure you properly COMMENT all of your methods.

Problem 2 (10 points): Create the MinHeap class and implement all of the methods. This class should extend the AbstractArrayBasedHeap and implement the MinHeapInterface. Remember to also override the toString() method as was done in MaxHeap.

Problem 3 (5 points): Create the MinHeapTester class and use it to test your MinHeap implementation by adding at least 5 Strings to the MinHeap, printing out the min heap, and then removing the minimum element from the min heap twice and printing out the resulting min heap. Make sure it looks as expected. Refer to the class slides that describe how the elements should be stored in the array to verify your code is working properly (i.e., the root is index 0, followed by the left and right children, then the left and right children of the next node, etc.).

Optional BONUS Problem (5 points). Create a Customer class with first name, last name, and ticket number. The ticket number holds the Integer value of a number used at the deli counter to see who is next in line. This class should implement the Comparable interface and use the ticket number attribute as the comparator (i.e., just have the compareTo() method call the compareTo() method on the ticket number Integer). You should also override the toString() method to return the first name, last name, and ticket number of the person. Create a Deli class that includes a MinHeap that will be used to hold Customer objects. Create an addCustomer() method that takes in a Customer as a parameter and adds it to the min heap. Create a public void processCustomers() method that removes each minimum ticket number customer from the min heap and prints them out (i.e., print them all out in order). Finally, create a DeliTester class in which you make up at least 5 customers, each with a ticket number, add them via the addCustomer() method, and then call the processCustomers() method. You should include these new classes in the same heap package as you did for the other problems.

***************AbstractArrayBasedHeap**********************

package heap;

public abstract class AbstractArrayBasedHeap {

/********* CLASS VARIABLES ************************************************/ protected E[] heap = null; protected static final int MIN_CAPACITY = 15;//min # elements in heap protected int capacity = MIN_CAPACITY; protected int heapSize = 0;//# of elements stored in heap /********* GETTERS AND SETTERS ********************************************/ /** * Uses lazy instantiation to create generic array to represent heap. Initialized * to the min capacity. * @return */ protected E[] getHeap() { if (heap == null){ Object[] o = new Object[MIN_CAPACITY]; heap = (E[])o;//need to cast since you can't initialize generic arrays } return heap; } protected void setHeap(E[] heap){ this.heap = heap; } public int getHeapSize(){ return heapSize; } public void setHeapSize(int heapSize){ this.heapSize = heapSize; } public int getCapacity(){ return capacity; }

/**************** METHODS *******************************************************/ /** * Compares the size of the heap to its current capacity. If the heap is more than * 75% full, it doubles its capacity. If it is lesss than 25% full, it halves * its capacity. It will never be less than the min capacity */ protected void updateCapacity(){ double percentFilled = (double)heapSize/capacity; if (percentFilled > .75){ increaseCapacity(); }else if (percentFilled < .25 && capacity > 2*MIN_CAPACITY){ decreaseCapacity(); } } /** * Creates a new array that is double the capacity of the current heap array, copies the * existing array's values into it, and then sets the new array as the heap. */ protected void increaseCapacity(){ Object[] o = new Object[getCapacity() *2]; E[] newHeap = (E[])o; for(int i=0; i < getHeapSize(); i++){ newHeap[i] = getHeap()[i]; } setHeap(newHeap); } /** * Creates a new array that is half the capacity of the current heap array copies the * existing array's values into it, and then sets the new array as the heap. */ protected void decreaseCapacity(){ Object[] o = new Object[getCapacity()/2]; E[] newHeap = (E[])o; for(int i=0; i < getHeapSize(); i++){ newHeap[i] = getHeap()[i]; } setHeap(newHeap); } /** * Calculates the parent index for the child index passed in. This is done * by subtracting 1 from the child index and then dividing this result by 2. * Since we are dividing two integers, the result will also be a truncated * integer. We must first check to see if the child index is the root (0), in * which case we return -1, indicating it is the root; * @return */ protected int calculateParentIndex(int childIndex){ int parentIndex = -1; //assumes childIndex is the root if (childIndex > 0){ parentIndex = (childIndex -1)/2; } return parentIndex; } /** * Calculates the left child index for the parent index passed in. This is done * by multiplying the parent index by 2 and adding 1. * @return */ protected int calculateLeftChildIndex(int parentIndex){ return parentIndex * 2 + 1; } /** * Calculates the left child index for the parent index passed in. This is done * by multiplying the parent index by 2 and adding 2. * @return */ protected int calculateRightChildIndex(int parentIndex){ return parentIndex * 2 + 2; } /** * Swaps the parent and child elements in the heap array. * @param parentIndex * @param childIndex */ protected void swap(int parentIndex, int childIndex){ E temp = getHeap()[parentIndex]; getHeap()[parentIndex] = getHeap()[childIndex]; getHeap()[childIndex] = temp; } }

***************MaxHeapTester******************************************

package heap;

public class MaxHeapTester { public void runTests(){ MaxHeap heap = new MaxHeap(); heap.addElement("John"); heap.addElement("Paul"); heap.addElement("George"); heap.addElement("Ringo"); heap.addElement("Elmer"); heap.addElement("Zorro"); System.out.println(heap); heap.removeMax(); System.out.println(heap); }

public static void main(String[] args) { MaxHeapTester mht = new MaxHeapTester(); mht.runTests();

}

}

****************MaxHeapInterface**********************************

package heap;

public interface MaxHeapInterface {

/** * Removes the maximum element from the heap and returns it. * @return */ public E removeMax(); /** * Adds the element passed in to the heap and puts it in its proper location in * the heap. * @param element */ public void addElement(E element); /** * Swaps the element at the index position passed in with the greater of its two * children if one of the children have a greater value. * @param index */ public void downMaxHeapify(int index); /** * Swaps the element at the index position passed in with its parent if the value * of the element stored at the index is larger than its parent. * @param index */ public void upMaxHeapify(int index);

}

*******************MaxHeap**********************

package heap;

public class MaxHeap extends AbstractArrayBasedHeap implements MaxHeapInterface{

@Override /** * Removes the root element from the max heap and returns it. In the process, * it replaces the root element with the last element in the heap and then calls * downMaxHeapify on it. */ public E removeMax() { E element = null; if (getHeapSize() > 0){ element = getHeap()[0]; getHeap()[0] = getHeap()[getHeapSize()-1];//bring last elemetn to top downMaxHeapify(0);//down heapify the root so it sinks to the proper location setHeapSize(getHeapSize()-1); } return element; }

@Override public void addElement(E element) { updateCapacity(); int nextIndex = getHeapSize(); getHeap()[nextIndex] = element; upMaxHeapify(nextIndex); setHeapSize(getHeapSize() + 1); }

@Override public void downMaxHeapify(int index) { int leftChildIndex = calculateLeftChildIndex(index); int rightChildIndex = calculateRightChildIndex(index); Comparable leftChild = null; Comparable rightChild = null; Comparable node = (Comparable)getHeap()[index]; if (leftChildIndex < getHeapSize()){ leftChild = (Comparable)getHeap()[leftChildIndex]; } if(rightChildIndex < getHeapSize()){ rightChild = (Comparable)getHeap()[rightChildIndex]; } int testIndex = index; if(leftChild != null && rightChild != null){ //both children exist...see which one is greater if(leftChild.compareTo(getHeap()[rightChildIndex]) < 0){ testIndex = rightChildIndex; }else{ testIndex = leftChildIndex; } }else if (leftChild != null){ //only left child exists testIndex = leftChildIndex; }else if(rightChild != null){ //only right child exists testIndex = rightChildIndex; } if (testIndex != index){ swap(index, testIndex); downMaxHeapify(testIndex); } } @Override public void upMaxHeapify(int index) { if (index > 0){ int parentIndex = calculateParentIndex(index); Comparable parentValue = (Comparable)(getHeap()[parentIndex]); E childValue = getHeap()[index]; if (parentValue.compareTo(childValue) < 0){ //parent less than child, so swap swap(parentIndex, index); upMaxHeapify(parentIndex); } } }

@Override public String toString() { StringBuffer buf = new StringBuffer(); buf.append("["); for (int i=0; i < getHeapSize(); i++){ buf.append(getHeap()[i]); if (i < getHeapSize()-1){ buf.append(","); } } buf.append("]"); return buf.toString(); } }