MaxHeap.javaFor this homework assignment, you will implement the max-heap data structure as we discussed in class.
This assignment consists of implementing the max-heap data structure, similar to what we described in class: every node will have a value that is \(\ge\) to the values of its child nodes. This can be used to implement the priority queue interface similar to Java’s built-in PriorityQueue (except that the built-in PriorityQueue defaults to using a min-heap). Similar to Homework 3 (when you implemented a DIY-version of an ArrayList), this will be a DIY-version of a heap.
There is no starter code for this assignment, so you’ll practice creating a program from scratch.
CompleteBinaryTree class we used in the code for Lecture 8R.left child, right child and parent indices of each node (in Lecture 8R).Comparable objects.Create a new file called MaxHeap.java (File -> New File; we recommend working within a folder called hw7 within your cs201 folder). Your MaxHeap class needs to be generic, similar to the CompleteBinaryTree covered in class. The generic type E should extends Comparable<E>, which means that E will have a compareTo method which can be used to determine if the heap property is satisfied. Again, CompleteBinaryTree would be a good starting point.
Your public MaxHeap class should have the following public methods:
MaxHeap(): default constructor, which initializes the internal ArrayList.boolean add(E item): add an item to the heap. This function always returns true after adding the item to the heap.void clear(): removes all elements from the queue. Do not iteratively call poll (there’s a simpler way).ArrayList<E> getData(): returns the ArrayList of data at the nodes. This is not in the PriorityQueue specification but will be used to test your implementation.int getMaxChildIndex(int i): returns the index of the child of node i with the maximum value. Note that this is not in the PriorityQueue specification, but it will be helpful when you write your poll method below. Be careful if node i does not have a left or right child. If it doesn’t have any child nodes (i.e. a leaf), return -1 to signal that it is a leaf. If there is only one child, this child has the maximum value, so return its index.E peek(): returns, but does not remove, the value at the top of the heap.E poll(): returns, and removes, the value at the top of the heap.int size(): returns the number of nodes in the heap.You should write comprehensive test cases for your MaxHeap in main, which will require calling all of the core methods. These are the requirements that you must meet in your test cases:
MaxHeap is initializedMaxHeapMaxHeap is clearedpeek is called on a MaxHeappoll is called at least 2 times on a MaxHeapsize is called on a MaxHeapThe examples we used in class would be good test cases. The toString method of the CompleteBinaryTree we used might also be helpful for debugging.
Checkstyle will run automatically when you submit to gradescope; up to 10% will be deducted by the autograder from the programming portion of your grade if you have > 2 types of checkstyle problems. Remember you can see more details on checkstyle on this page, including how to run it in vscode.
Note that because starter code is not provided for this assignment, you will need to write all of your javadoc comments from scratch!
I will do a manual review for design. Up to 5% may be deducted from your final score due to design problems. This will also include checking the quality (rather than just the form) of your javadoc comments!