Question

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<K extends Comparable<K>> implements PriorityQueue<K> {
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<K extends Comparable<K>> implements PriorityQueue<K> {
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<String> pq = new HeapPriorityQueue<>();
  PriorityQueue<String> pqU = new PQunsorted<>();
  PriorityQueue<String> 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(
                                  "\nProgram 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() + "\n");
     break;
    }
   } catch (Exception e) {
    System.out.println("Error " + e.toString());
   }
  }
  sc.close();
}

//PriorityQueue

package class17;

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

//HeapPriorityQueue

package class17;

import java.util.Iterator;

public class HeapPriorityQueue<K extends Comparable<K>> implements
      PriorityQueue<K> {
   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<K> 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");
   }

}

Answer 1

the code is correct

import java.util.Scanner;

import class17.HeapPriorityQueue;
import class17.PriorityQueue;
******************************************************************/
class PQunsorted<K extends Comparable<K>> implements PriorityQueue<K> {
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<K extends Comparable<K>> implements PriorityQueue<K> {
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<String> pq = new HeapPriorityQueue<>();
PriorityQueue<String> pqU = new PQunsorted<>();
PriorityQueue<String> 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(
"\nProgram 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() + "\n");
break;
}
} catch (Exception e) {
System.out.println("Error " + e.toString());
}
}
sc.close();
}
//PriorityQueue
package class17;
public interface PriorityQueue<K extends Comparable<K>> {
public void insert(K x) throws Exception;
public K removeMin() throws Exception;
}
//HeapPriorityQueue
package class17;
import java.util.Iterator;
public class HeapPriorityQueue<K extends Comparable<K>> implements
PriorityQueue<K> {
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<K> 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");
}
}