import java.util.Scanner; import class17.HeapPriorityQueue; import class17.Prior
ID: 3866609 • Letter: I
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(
" 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<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");
}
}
Explanation / Answer
Java:
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 {
if (size == 0) throw new Exception("Queue Empty");
// let min be first element
K min=data[0];
int removeIndex=0;
//update min iterating through rest of
//array
for(int i=1;i<size;i++){
if(data[i].compareTo(min)<0)
{
min=data[i];
removeIndex=i;
}
}
//delete min from removeIndex
for(int i=removeIndex;i<size-1;i++)
data[i]=data[i+1];
size--;
return min;
}
}
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 {
if (size >= capacity) throw new Exception("Queue full");
K temp;
if(size==0||x.compareTo(data[size-1])<=0)
data[size++]=x;
else {
for(int i=0;i<size;i++){
if(x.compareTo(data[i])>=0){
//move elements to right
for(int j=size;j>i;j--)
data[j]=data[j-1];
data[i]=x;
size++;
break;
}
}
}
}
// easy removal in this implementation
public K removeMin() throws Exception {
if (size == 0) throw new Exception("Queue Empty");
return data[--size];
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.