PLEASE DO CORRECTLY!!! The main goal of this is to implement methods that perfor

Question

PLEASE DO CORRECTLY!!!

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.

words.doc

----------------------------------------------------------------------------------------

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

Explanation / Answer

import java.util.Arrays; public class BinaryHeap implements PriorityQueue { private static final int DEFAULT_CAPACITY = 10; protected T[] array; protected int size; /** * Constructs a new BinaryHeap. */ @SuppressWarnings("unchecked") public BinaryHeap () { // Java doesn't allow construction of arrays of placeholder data types array = (T[])new Comparable[DEFAULT_CAPACITY]; size = 0; } /** * Adds a value to the min-heap. */ public void add(T value) { // grow array if needed if (size >= array.length - 1) { array = this.resize(); } // place element into heap at bottom size++; int index = size; array[index] = value; bubbleUp(); } /** * Returns true if the heap has no elements; false otherwise. */ public boolean isEmpty() { return size == 0; } /** * Returns (but does not remove) the minimum element in the heap. */ public T peek() { if (this.isEmpty()) { throw new IllegalStateException(); } return array[1]; } /** * Removes and returns the minimum element in the heap. */ public T remove() { // what do want return? T result = peek(); // get rid of the last leaf/decrement array[1] = array[size]; array[size] = null; size--; bubbleDown(); return result; } /** * Returns a String representation of BinaryHeap with values stored with * heap structure and order properties. */ public String toString() { return Arrays.toString(array); } /** * Performs the "bubble down" operation to place the element that is at the * root of the heap in its correct place so that the heap maintains the * min-heap order property. */ protected void bubbleDown() { int index = 1; // bubble down while (hasLeftChild(index)) { // which of my children is smaller? int smallerChild = leftIndex(index); // bubble with the smaller child, if I have a smaller child if (hasRightChild(index) && array[leftIndex(index)].compareTo(array[rightIndex(index)]) > 0) { smallerChild = rightIndex(index); } if (array[index].compareTo(array[smallerChild]) > 0) { swap(index, smallerChild); } else { // otherwise, get outta here! break; } // make sure to update loop counter/index of where last el is put index = smallerChild; } }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.