The main goal of this is to implement methods that perform heap operations.
Add a class named BinaryHeap to the project. This class supports the array representation of binary max heaps. Generic code is optional, apply String values for data, and apply the compareTo( ) method for comparison.
The class shall contain the int field manyItems as usual, and an array field to store the data. Add a constructor to the class to such that is instantiates the array to an initial length (parameter).
Implement the add( ) method which in turn applies the upward reheapification algorithm.
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.
(Implement a static method named heapFactory ( ). The method takes an array of 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.
Implement a method trim3( ) such that it removes the three largest elements 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.
Add an application class to the project and test your methods. This class displays the heap array by calling the toString( ) method
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.
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