Please use ArrayList as the assignment states. (I will be using import java.util.*)

This is the method for the BinaryHeap =

public BinaryHeap(int initial_capacity, boolean max){

Here is the testing code as an example:

public static void main(String[] args){ BinaryHeap heap = new BinaryHeap(2,false); heap.push("a"); heap.push("b"); heap.push("c"); heap.push("e"); heap.push("d"); while (heap.size() > 0){ System.out.println(heap.pop()); } //Should print a,b,c,d,e heap = new BinaryHeap(2,true); heap.push("a"); heap.push("b"); heap.push("c"); heap.push("e"); heap.push("d"); while (heap.size() > 0){ System.out.println(heap.pop()); } //should print e,d,c,b,a } }

Heaps and Graphs - Part 1 In this assignment you will be making a max-heap (and min-heap), for the sake of making a priority queue. Later, we will be using this to make a priority queue, which we still later yet even use to find the optimal path through a graph. In this assignment you will Make a generic binary max-heap Add a flag that allows the binary heap to function as a min heap as well as a max heap Test this on a number of different inputs . Heap First, we start by making our heap. In a standard BinaryHeap we store everything in an array Remember, a heap is a tree, but due to its properties it is a complete tree every level of the tree except the last is full, and the last level has all of the leaves as far left as possible Because of this completeness, we can efficiently store our tree in an array. Due to the handling of generics in Java, we will be using an ArrayList as our internal representation For our Heap, we will need int capacity the capacity of our ArrayList ArrayList heap-our internal representation of the heap int last-the last spot added to in our heap int minorMax-an integer that we will use to modify our comparisons to allow for our heap to operate as a min-heap or a max-heap When constructing our heap we will want to Construct a new ArrayList for our heap to a supplied initialCapacity Loop through the capacity and add null values to the heap Set the last index to the initial spot (which should be 0 at this time) . Set the minOrMax variable based on a supplied boolean isMax that will be true when constructing a max heap and false when constructing a min heap o We will be multiplying minOrMax by the results of our comparisons o Recall that A.compareTo(B) returns -1 when A is less than B and 1 when A is greater than B All of our comparisons will be of the form o (A.compareTo(B)*minOrMax) So, if minOrMax is positive it will operate in the normal way, but if it is negative then it will flip if so that it will be -1 when A is greater than B and 1 when A is less than B We want minOrMax to operate normally when isMax is true, and in the opposite way when isMax is false o o We will now need to implement the following functions . public void push (T entry)_This will add a new element to the heap and then work its way up from the bottom of the heap up to the root, making sure it keeps the properties of a heap . protected void makeSafe)This will be called at the end of the push, and will make sure that the heap is of sufficient size to handle future pushes . public T pop()-This will remove the top element of the heapthe root-and will then move the last element in the heap up to the heap, working its way back down the heap to keep the properties of the heap intact public int size() _This will return the size of heap (the number of elements currently in the heap, which is not necessarily the capacity [in fact it should never be the capacity]) . Size Return the number of elements found in the heap (this will be something based on last and not based on the capacity) Push To push to the binary heap we will need to Increment the last counter to point to the new spot where we will be adding the new element set the last element of the heap to the new value We will then start at the current element (initially this new last element) While this current index is greater than the root value we will . o Get the value at the parent index (recall where the parent is found in comparison to the current index) If the parent value is less than the current value then swap them (you will want to use.set) o Otherwise, break out of the loop Set the current index to the parent index and then loop o After the loop has finished, call the helper makeSafe function MakeSafe When adding to a heap, we need to make sure that we can accept new things. we will periodically need to resize our internal heap when we hit our capacity To ensure this, Check to see if the last index is at the limit of the capacity . o If it is, then we need to increase the size of our heap Loop through for the current capacity and add null values to the end of the ArrayList Then update our capacity to be twice what it previously was Pop To remove from our heap, we will be returning the element at the top of our heap (the maximal value for a max-heap and vice-versa for a min-heap) Save the value at the root of the heap to return at the end of the method . Set the root value of the heap to be the last element in the heap and then remove the last element of the heap (by setting the last element to be null) Decrement the last index (since we have shrunk our heap) . Set a current index to be at the root While the current still has a child (i.e. while current#2 >-last) o Get the left and right indices and the left and right values (remember that the left o By default assume that the left child is the larger child and set biggerIndex to be o If the right child is not null and it is bigger than the left value, then set the o If the parent is bigger than biggerValue, then break the loop child is at 2*current and the right is at 2*current 1 the left index and biggerValue to be the left value biggerIndex to be the right index and the biggerValue to the right value Else, swap the parent with the bigger (set the parent to be the biggerValue and the biggerlndex to be the parent value) and set the current index to be the biggerlnde:x o Finally, return the initial saved value Testing Test your code and make sure you are happy with how it is working. Part 2 wll follow soon. Heaps and Graphs - Part 1 In this assignment you will be making a max-heap (and min-heap), for the sake of making a priority queue. Later, we will be using this to make a priority queue, which we still later yet even use to find the optimal path through a graph. In this assignment you will Make a generic binary max-heap Add a flag that allows the binary heap to function as a min heap as well as a max heap Test this on a number of different inputs . Heap First, we start by making our heap. In a standard BinaryHeap we store everything in an array Remember, a heap is a tree, but due to its properties it is a complete tree every level of the tree except the last is full, and the last level has all of the leaves as far left as possible Because of this completeness, we can efficiently store our tree in an array. Due to the handling of generics in Java, we will be using an ArrayList as our internal representation For our Heap, we will need int capacity the capacity of our ArrayList ArrayList heap-our internal representation of the heap int last-the last spot added to in our heap int minorMax-an integer that we will use to modify our comparisons to allow for our heap to operate as a min-heap or a max-heap When constructing our heap we will want to Construct a new ArrayList for our heap to a supplied initialCapacity Loop through the capacity and add null values to the heap Set the last index to the initial spot (which should be 0 at this time) . Set the minOrMax variable based on a supplied boolean isMax that will be true when constructing a max heap and false when constructing a min heap o We will be multiplying minOrMax by the results of our comparisons o Recall that A.compareTo(B) returns -1 when A is less than B and 1 when A is greater than B All of our comparisons will be of the form o (A.compareTo(B)*minOrMax) So, if minOrMax is positive it will operate in the normal way, but if it is negative then it will flip if so that it will be -1 when A is greater than B and 1 when A is less than B We want minOrMax to operate normally when isMax is true, and in the opposite way when isMax is false o o We will now need to implement the following functions . public void push (T entry)_This will add a new element to the heap and then work its way up from the bottom of the heap up to the root, making sure it keeps the properties of a heap . protected void makeSafe)This will be called at the end of the push, and will make sure that the heap is of sufficient size to handle future pushes . public T pop()-This will remove the top element of the heapthe root-and will then move the last element in the heap up to the heap, working its way back down the heap to keep the properties of the heap intact public int size() _This will return the size of heap (the number of elements currently in the heap, which is not necessarily the capacity [in fact it should never be the capacity]) . Size Return the number of elements found in the heap (this will be something based on last and not based on the capacity) Push To push to the binary heap we will need to Increment the last counter to point to the new spot where we will be adding the new element set the last element of the heap to the new value We will then start at the current element (initially this new last element) While this current index is greater than the root value we will . o Get the value at the parent index (recall where the parent is found in comparison to the current index) If the parent value is less than the current value then swap them (you will want to use.set) o Otherwise, break out of the loop Set the current index to the parent index and then loop o After the loop has finished, call the helper makeSafe function MakeSafe When adding to a heap, we need to make sure that we can accept new things. we will periodically need to resize our internal heap when we hit our capacity To ensure this, Check to see if the last index is at the limit of the capacity . o If it is, then we need to increase the size of our heap Loop through for the current capacity and add null values to the end of the ArrayList Then update our capacity to be twice what it previously was Pop To remove from our heap, we will be returning the element at the top of our heap (the maximal value for a max-heap and vice-versa for a min-heap) Save the value at the root of the heap to return at the end of the method . Set the root value of the heap to be the last element in the heap and then remove the last element of the heap (by setting the last element to be null) Decrement the last index (since we have shrunk our heap) . Set a current index to be at the root While the current still has a child (i.e. while current#2 >-last) o Get the left and right indices and the left and right values (remember that the left o By default assume that the left child is the larger child and set biggerIndex to be o If the right child is not null and it is bigger than the left value, then set the o If the parent is bigger than biggerValue, then break the loop child is at 2*current and the right is at 2*current 1 the left index and biggerValue to be the left value biggerIndex to be the right index and the biggerValue to the right value Else, swap the parent with the bigger (set the parent to be the biggerValue and the biggerlndex to be the parent value) and set the current index to be the biggerlnde:x o Finally, return the initial saved value Testing Test your code and make sure you are happy with how it is working. Part 2 wll follow soon