import java.util.Scanner; import class17.HeapPriorityQueue; import class17.PriorityQueue; /*************** * Homework D * * Edit the following file and save it as Dxxxxxxxx.java where xxxxxxxx is * replaced by your 8 digit ID number. Change the class name to reflect this * file name. Include a comment with your name at the top of the program in case * there is a problem with automatic recognition of your ID number. Submit this * one file as an email attachment to alexander.ryba@qc.cuny.edu * * 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(); } } 

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

import java.util.Iterator;

import java.util.Scanner;

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");

}

}-------------------------------------------------------------------------------------

package class17;

public interface PriorityQueue> {

public void insert(K x) throws Exception;

public K removeMin() throws Exception;

}

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

please give the java code that runs. thankyou