Part 1: Setup and test classes Heap and HeapSort. For this assignment, we use classes: Heap.java (listing 23.10, page 878) and HeapSort.java (listing 23.10, page 879). The second file code is separated into to 2 files: HeapSort.java and TestHeapSort.java. These three files are provided with the assignment. Download these three files, compile and run class TestHeapSort.java. This class uses hard coded data for illustration purpose only. Notice the text data is of object type, not primitive types. Part 2 (100 points): Implement Priority Queue using Heap structure. Download and complete the implementation of class PQ_Heap.java, provided with this assignment. The only data member we need for this class is a heap object created from class Heap.java in part 1 above. Hint: Create the heap object as private data member in file PQ_Heap.java; Then use the methods in class Heap.java to implement the priority queue methods outlined in file PQ_Heap.java by applying the heap methods on the heap object. In other words, implement class PQ_Heap using methods in class Heap. It is recommended that you implement class PQ_Heap.java as a template class, similar to class Heap.java. In addition, to implement all priority queue methods outlined in class PQ_Heap.java, you may need to include additional methods to template class Heap.java. Next, create the new test file TestPQH.cpp to test class PQ_Heap.java. Use the following menu options as shown (No menu, no points!). Force the user to start with option 0 to select the data type of the priority queue content. Then allow the user to exercise other options on the selected queue type. ----------------MAIN MENU--------------- 0. Enter Queue Type (integer or string) 1. Enqueue Element 2. Dequeue Element 3. Check is_Full 4. Check is_Empty 5. Print PQueue Size 6. Display Front Element 7. Print PQueue Elements 8. Exit program Enter option number:

Always re-display the menu after an option (other than option 8) is fully exercised with blank lines before and after the menu.

For option 7, print the PQ content as shown below. Notice that value 99 below is the parent node for values 66 (left child) and 44 (right child); value 66 is the parent node for values 33 (left child) and 22 (right child); Nodes 44, 33, and 22 have no child nodes in the heap. Index 0: 99 66 44 Index 1: 66 33 22 Index 2: 44 Index 3: 33 Index 4: 22

Heap class

// Class Heap.java // Textbook - Listing 23.9, Page 878

public class Heap> { private java.util.ArrayList list = new java.util.ArrayList();

/** Create a default heap */ public Heap() { }

/** Create a heap from an array of objects */ public Heap(E[] objects) { for (int i = 0; i < objects.length; i++) add(objects[i]); }

/** Add a new object into the heap */ public void add(E newObject) { list.add(newObject); // Append to the heap int currentIndex = list.size() - 1; // The index of the last node

while (currentIndex > 0) { int parentIndex = (currentIndex - 1) / 2; // Swap if the current object is greater than its parent if (list.get(currentIndex).compareTo( list.get(parentIndex)) > 0) { E temp = list.get(currentIndex); list.set(currentIndex, list.get(parentIndex)); list.set(parentIndex, temp); } else break; // the tree is a heap now

currentIndex = parentIndex; } }

/** Remove the root from the heap */ public E remove() { if (list.size() == 0) return null;

E removedObject = list.get(0); list.set(0, list.get(list.size() - 1)); list.remove(list.size() - 1);

int currentIndex = 0; while (currentIndex < list.size()) { int leftChildIndex = 2 * currentIndex + 1; int rightChildIndex = 2 * currentIndex + 2;

// Find the maximum between two children if (leftChildIndex >= list.size()) break; // The tree is a heap int maxIndex = leftChildIndex; if (rightChildIndex < list.size()) { if (list.get(maxIndex).compareTo( list.get(rightChildIndex)) < 0) { maxIndex = rightChildIndex; } }

// Swap if the current node is less than the maximum if (list.get(currentIndex).compareTo( list.get(maxIndex)) < 0) { E temp = list.get(maxIndex); list.set(maxIndex, list.get(currentIndex)); list.set(currentIndex, temp); currentIndex = maxIndex; } else break; // The tree is a heap }

return removedObject; }

/** Get the number of nodes in the tree */ public int getSize() { return list.size(); } }

HeapSort class

// Class Heap.java // Textbook - Listing 23.9, Page 878

public class HeapSort { /** Heap sort method */ public static > void heapSort(E[] list) { // Create a Heap of integers Heap heap = new Heap(); // Add elements to the heap for (int i = 0; i < list.length; i++) heap.add(list[i]); // Remove elements from the heap for (int i = list.length - 1; i >= 0; i--) list[i] = heap.remove(); } /** A test method */ public static void main(String[] args) { Integer[] list = {-44, -5, -3, 3, 3, 1, -4, 0, 1, 2, 4, 5, 53}; System.out.print("Original List:\t"); //print original list for (int i = 0; i < list.length; i++) System.out.print(list[i] + " "); heapSort(list); //sort the list System.out.print(" Sorted List:\t"); //print original list for (int i = 0; i < list.length; i++) System.out.print(list[i] + " "); } }

PQ_Heap class

// Generic code for class priority_queue_heap for Assignment 5

public class PQ_heap { // Constructor method PQ_heap() {}; // Return true if priority queue is empty; otherwise return false public boolean is_empty() {}; // Return true if priority queue is full; otherwise return false public boolean is_full() {};

// Return (don't remove) the front element from the priority queue // Precondition: priority queue is not empty. public int front() {};

// return number of elements in the queue public int size() {}; // Remove the largest value from this priority queue and return it. // Precondition: priority queue is not empty. public int dequeue() {};

// Inserts the 'value' into the priority queue. // Precondition: priority queue is not full public void enqueue(int value) {}; };

Note: The PQ_heap have to be generic. Can you please do it using the classes I provide(Heap class, HeapSort class, PQ_heap class) and it is Data structures class in java language please please and thank you so much.