Java Exercises
Requirements
The main goal of this assignment is to implement methods that perform heap operations.
Add a class named BinaryHeap to the project. This class supports the arrayrepresentation of binary max heaps. Generic code is optional. If you opt out generic, apply String values for data, and apply the compareTo( ) method for comparison.
The class shall contain the int type field manyItems as usual, and an array field to store the data. Add a constructor to the class such that it instantiates the array to an initial length (parameter).
Implement the add( ) method which in turn applies the upward reheapificationalgorithm.
Implement the removeRoot( ) method such that it applies the downward reheapification algorithm.
Add ensureCapacity ( ) and toString( ) to the class. You shall decide how your toString traverses the tree. Describe your choice in a comment attached to the method.
ImplementastaticmethodnamedbuildHeap().Themethodtakesanarrayof Strings for parameter (the parameter is not necessarily a heap). The method instantiates a String array to the length of the parameter array and constructs a heap on this array such that calling the add() method repeatedly, adds all the parameter elements one after each other to the new heap. The method must also work if the heap is empty. It is a precondition, however, that the base array of the heap is not null.
Note 1: The buildHeap( ) method will look familiar when you see it again as part of the heap sort algorithm. It will be a private helper method named makeHeap( ). See also makeHeap( ) in the book, p 656.
Determine the performance of the buildHeap method.
Note 2: You may follow the hints in the book for Programming Project #5, p672, and implement a second solution for buildHeap( ), which performs O(n) better than the recommended solution above.
Implementamethodtrim3()suchthatitremovesthethreelargestelements from this heap. The method should work (remove elements) in a sensible way even if the heap has no element, 1 element or 2 elements only.
Note that the largest element is obviously at the root. The second largest must be one of the two children of the root. The third largest is not necessarily the other child, it can be a grandchild of the root.
9. Add an application class to the project and test your methods. This class displays the heap array by calling the toString( ) method.
10. You may add more methods if you see it necessary, but you must have all the methods implemented as listed above.
It is recommended to add to the class the private methods below:
swap(), to exchange array entries at two given indices·
reheapUp(), to do the upward reheapification from a given index·
reheapDown(), to do the downward reheapification from a given index (make it·recursive)
These method simplify the implementation of the add() and removeRoot() methods, they are particularly useful if you want to implement a general remove() method (optional).
11.The words.doc file attached to the assignment can be used for testing purposes, but you can use your own choice of text. The text must have at least 40 different meaningful words, all pairwise different with respect to compareTo().
This is the word document:
a A
be Be
cat Cat
door Door
error Error
four Four
garage Garage
home Home
island Island
jam Jam
kick Kick
lobby Lobby
mouse Mouse
norm Norm
otter Otter
purr Purr
queue Queue
robin Robin
silver Silver
tally Tally
urgent Urgent
verb Verb
willow Willow
x-ray X-ray
yard Yard
zebra Zebra