Reference no: EM132095157

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