Just as it was possible to create more efficient linear data structures, the stack and queue, when the types of operations were restricted, it is possible to create more efficient tree data structures with restricted operations. When only the minimum or maximum valued object of a collection is accessed a min heap or a max heap can provide constant find operations. In this lab you will implement an array-based binary max heap.
The file MaxHeap.java contains the outline for an array-based implementation of a binary max heap. Like many of the collection data structures you have programmed this semester, the max heap has methods for adding, removing, and getting. For a max heap these methods are called insert, deleteMax, and findMax. Before beginning on these methods add instance data and complete the constructor and the toString method. Next, write the insert method. This method should add the specified object in the next available location and then heapify up the tree. Note that when heapifying up the tree it is not always necessary to ascend to the root. In order to make your code efficient, the heapify up should stop as soon as the heap is valid. Be sure to thoroughly test before proceeding.
Next, complete the findMax and size methods. If your add method is functioning properly these methods should be trivial. Note, however, the findMax method throws an exception if it is not possible to return the maximum. Be sure to test for this case and throw an appropriate exception. Before proceeding, be sure to test the findMax method both when it is empty and when it is not.
Finally, complete the deleteMax method. This method should store the root of the tree in a variable, remove the highest indexed object, replace the root with the removed object, and then heapify down the tree. Note, just like when inserting the most efficient implementation will stop heapifying down the tree as soon as the heap is valid and like when finding an exception is should be thrown when the heap is empty . Remember to code in small pieces and test thoroughly.
To submit your code: Tar your lab13 directory and submit your code on the course Inquire site.