Homework 7

due: Thursday April 17 at 11:59pm (submit on Gradescope here).

Goals:

• Develop your own program from scratch.
• Practice designing a class to be generic.
• Represent a complete binary tree using an array.
• Implement your own max-heap data structure.

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.

Suggestions:

• A good starting point would be the CompleteBinaryTree class we used in the code for Lecture 8W.
• Revisit how we calculated the left child, right child and parent indices of each node (in Lecture 8W).
• Review slides 7 - 8 (pages 7 - 14) on the "heapify-up" algorithm, and slide 11 (pages 17) on the "heapify-down" algorithm (Lecture 8W).
• Review slides 10 - 11 from Lecture 4W about Comparable objects.

Requirements:

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 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.

Submission

Upload MaxHeap.java to Gradescope and remember to check the style of your code. Remember to include Javadoc comments including one in the header that describes what the file is and includes the @author tag.

There is also an optional challenge problem if you're looking for more fun and practice.