import java.util.Scanner; import class17.HeapPriorityQueue; import class17.PriorityQueue;

/*************** * Homework D * * * Remove any initial package declaration that might be added to your file in * case you edit it in eclipse. * * The goal of the homework is to create two ArrayList based implementations of * a Priority Queue as explained in Section 9.2 (in 9.2.4 and 9.2.5) of the * textbook. * * These are to be made by completing the classes PQunsorted and PQsorted as * given below. In completing these classes you should only use the instance * members array, capacity and size, but you should add implementations for the * required Priority Queue methods. Only change their methods as indicated by * TODO instructions * * Finally, you should make the main program display your name and 8 digit ID * number. * * Your implementations should work interchangeably with the heap based version. * The main program runs both your implementations and the (correct) heap based * one from class at once. When your code is correct, it should produce any * output three times over. ********************************************************************/

class PQunsorted> implements PriorityQueue { K[] data; int size; int capacity;

public PQunsorted() { capacity = 100; size = 0; data = (K[]) new Comparable[capacity]; } // easy insertion public void insert(K x) throws Exception { if (size >= capacity) throw new Exception("Queue full"); data[size++] = x; }

public K removeMin() throws Exception { // TODO complete code to remove min here return null; } }

class PQsorted> implements PriorityQueue { K[] data; int size; int capacity;

public PQsorted() { capacity = 100; size = 0; data = (K[]) new Comparable[capacity]; } public void insert(K x) throws Exception { // TODO complete code to insert x, keeping the array sorted so the min is at the end

}

// easy removal in this implementation public K removeMin() throws Exception { if (size == 0) throw new Exception("Queue Empty"); return data[--size]; } }

// ---------------------- main program to test implementations ---

class D00000000 { public static void main(String args[]) { PriorityQueue pq = new HeapPriorityQueue<>(); PriorityQueue pqU = new PQunsorted<>(); PriorityQueue pqS = new PQsorted<>(); boolean done = false; Scanner sc = new Scanner(System.in); while (!done) { try { // add your name into the following print statement System.out.println( " Program by: xxxx ---- cmds are + - Q: >>"); String cmd = sc.next(); String entry = null; char command = cmd.charAt(0); if (command == '+') entry = sc.next(); switch (cmd.charAt(0)) { case 'Q': done = true; break; case '+': pq.insert(entry); pqU.insert(entry); pqS.insert(entry); break; case '-': System.out.print(pq.removeMin() + " "); System.out.print(pqU.removeMin() + " "); System.out.print(pqS.removeMin() + " "); break; } } catch (Exception e) { System.out.println("Error " + e.toString()); } } sc.close(); }

//PriorityQueue

package class17;

public interface PriorityQueue> { public void insert(K x) throws Exception; public K removeMin() throws Exception; }

//HeapPriorityQueue

package class17;

import java.util.Iterator;

public class HeapPriorityQueue> implements PriorityQueue { private K data[]; private int size; private int capacity;

// constructors public HeapPriorityQueue() { capacity = 100; size = 0; data = (K[]) new Comparable[capacity]; }

public HeapPriorityQueue(int c) { capacity = c; size = 0; data = (K[]) new Comparable[capacity]; }

// required priority queue methods public void insert(K x) throws Exception { if (size >= capacity - 1) throw new Exception("Priority Queue Full"); data[size++] = x; bubbleUp(size - 1); }

public K removeMin() throws Exception { if (size <= 0) throw new Exception("Priority Queue Empty"); swapData(0, --size); bubbleDown(0); return data[size]; }

// auxiliary utility methods private void swapData(int n, int m) { K temp = data[n]; data[n] = data[m]; data[m] = temp; }

private void bubbleUp(int n) { if (n <= 0) return; // at root K dn = data[n]; K dp = data[(n - 1) / 2]; // parent data if (dn.compareTo(dp) >= 0) return; // no problems swapData(n, (n - 1) / 2); bubbleUp((n - 1) / 2); }

public void bubbleDown(int n) { if (2 * n + 1 >= size) return; // at leaf K dn = data[n]; K dl = data[2 * n + 1]; // left child K dr = dl; if (2 * n + 2 < size) dr = data[2 * n + 2]; // right child if (dn.compareTo(dl) < 0 && dn.compareTo(dr) < 0) return; // no problems if (dr.compareTo(dl) < 0) { swapData(n, 2 * n + 2); bubbleDown(2 * n + 2); } else { swapData(n, 2 * n + 1); bubbleDown(2 * n + 1); } }

// heap creation public void heapify(Iterator x) throws Exception { while (x.hasNext()) { if (size + 1 == capacity) break; data[size++] = x.next(); } int n = size / 2; while (--n >= 0) bubbleDown(n); if (x.hasNext()) throw new Exception("Heap is Full"); }

}