due: Friday November 8th at 11:59pm (submit on Gradescope here).
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 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; I would also 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 must demonstrate that you have tested your code in a public static void main. Do not rely on Gradescope to test your code. The examples we used in class would be good test cases. The toString method of the CompleteBinaryTree we used might also be helpful for debugging.
The final requirement is to add javadoc-style documentation for every method as in Homework 3.
Please upload MaxHeap.java to Gradescope and remember to check the style of your code.
There is also an optional challenge problem if you're looking for more practice.
Last updated: 2024-12-10