1.

import java.util.*

public class Exercises18HPQ {

public static void main(String[] args) { // BJP HeapPriorityQueue modified: HeapPriorityQueue pq18 = new HeapPriorityQueue(100); pq18.add(88); pq18.add(-1); pq18.add(35); pq18.add(42); pq18.add(42); System.out.println(pq18); // uses PQ toString() // Some more Oracle Java methods: System.out.println(Arrays.toString(pq18.toArray())); // PQ return and Array System.out.println(pq18.remove(42)); // removes just a single Object System.out.println(pq18); // uses PQ toString() System.out.println(pq18.remove(99)); // removes just a single Object System.out.println(pq18); // uses PQ toString() System.out.println(pq18.poll()); // Oracle PQ actually uses poll to remove System.out.println(pq18); // uses PQ toString() pq18.clear(); // clears the Queue System.out.println(pq18); // noting left at this point // Some CONSTRUCTOR options with Oracle Java HeapPriorityQueue: // Build a Collection to use in testing below Collection storage = new ArrayList(); storage.add(42); storage.add(17); storage.add(9); storage.add(42); storage.add(35); storage.add(-1); storage.add(88); System.out.println(storage); // output simply in order of above input // Oracle Java HeapPriorityQueue has constructor to accept Collection: HeapPriorityQueue pq = new HeapPriorityQueue(storage); System.out.println(pq); // prints as internal array order (KNOW what this is!!!) while (!pq.isEmpty()) { System.out.print(pq.remove() + " "); // prints in "natural" order } System.out.println();

// Oracle Java HeapPriorityQueue has constructor to accept a different Comparator: HeapPriorityQueue pqMax = new HeapPriorityQueue(Collections.reverseOrder()); pqMax.add(88); pqMax.add(-1); pqMax.add(35); pqMax.add(42); pqMax.add(9); pqMax.add(17); pqMax.add(42); System.out.println(pqMax); // prints as internal array order while (!pqMax.isEmpty()) { System.out.print(pqMax.remove() + " "); // prints in Comparator's order } System.out.println();

} }

2.

import java.util.Arrays; import java.util.Collection; import java.util.Comparator; import java.util.NoSuchElementException;

public class HeapPriorityQueue> { private E[] elementData; private int size; // Constructs an empty queue. @SuppressWarnings("unchecked") public HeapPriorityQueue() { elementData = (E[]) new Comparable[10]; // was Object size = 0; } // ADD METHODS HERE for exercise solutions: // Adds the given element to this queue. public void add(E value) { // resize if necessary if (size + 1 >= elementData.length) { // O(N) issue here elementData = Arrays.copyOf(elementData, elementData.length * 2); } // insert as new rightmost leaf elementData[size + 1] = value; // "bubble up" toward root as necessary to fix ordering int index = size + 1; boolean found = false; // have we found the proper place yet? while (!found && hasParent(index)) { int parent = parent(index); if (elementData[index].compareTo(elementData[parent])

// move rightmost leaf to become new root elementData[1] = elementData[size]; size--; // "bubble down" root as necessary to fix ordering int index = 1; boolean found = false; // have we found the proper place yet? while (!found && hasLeftChild(index)) { int left = leftChild(index); int right = rightChild(index); int child = left; if (hasRightChild(index) && elementData[right].compareTo(elementData[left]) 0) { swap(elementData, index, child); index = child; } else { found = true; // found proper location; stop the loop } } return result; } // Returns the number of elements in the queue. public int size() { return size; } // Returns a string representation of this queue, such as "[10, 20, 30]"; // The elements are not guaranteed to be listed in sorted order. public String toString() { String result = "["; if (!isEmpty()) { result += elementData[1]; for (int i = 2; i 1; } // returns true if the node at the given index has a non-empty left child private boolean hasLeftChild(int index) { return leftChild(index)

}

Complete Programming Project #3, page 1118 in BJP text (add Constructors and methods to text provided Heap data structure Class) Submit Heap Priority Queue.java This project in text asks us to make the textbook example HeapPriorityQueue.java work similar to the Oracle Java PriorityQueue. So lets start with the following test code Exercises18.java that should work as is with Oracle Priority Queue. That's the easy part. Now change all the Oracle "Priority Queue" identifiers to "Heap Priority Queue" as in the following test code Exercises18 HPQ.java B and now the work starts here!!! You will need to add the following code elements: 1. toArray() method 2. remove(Object) method to remove first occurrence of the provided object 3. poll() is used by Oracle 4. clear() simply clears all the data 5. HeapPriorityQueue(Collection) constructor loads up all the data from the provided Collection 6. Heap PriorityQueue(Comparator) constructor that allows us to reverse into a max heap It's actually just this last item (max heap) that the author of text is after here, but I wanted to start us off with some easier exercises, just to get into how this data structure is structured. Bottom line: Fix the textbook code HeapPriorityQueue.java so that Exercises18HPQ.java produces the output: [-1, 42, 35, 88, 42] [-1, 42, 35, 88, 42] true [-1, 42, 35, 88] false [-1, 42, 35, 88) -1 [35, 42, 88] [] [42, 17, 9, 42, 35, -1, 88] [-1, 35, 9, 42, 42, 17, 88] -1 9 17 35 42 42 88 [88, 42, 42, -1, 9, 17, 35] 88 42 42 35 17 9 -1