--------------------------------------------------------------------------------
ID: 3827187 • Letter: #
Question
-----------------------------------------------------------------------------------------
import java.util.Iterator;
import java.util.Scanner;
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");
}
}-------------------------------------------------------------------------------------
package class17;
public interface PriorityQueue<K extends Comparable<K>> {
public void insert(K x) throws Exception;
public K removeMin() throws Exception;
}
-----------------------------------------------------------
please give the java code that runs. thankyou
Explanation / Answer
PROGRAM CODE:
package queue;
public 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 {
K min = data[0];
int index = 0;
for(int i=0; i<size; i++)
{
if(min.compareTo(data[i]) <0)
{
min = data[i];
index = i;
}
}
while(index < size-1)
{
data[index] = data[index+1];
index++;
}
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 == 0)
data[size] = x;
else
{
int index = 0;
for(int i=0; i<size; i++)
{
if(data[i].compareTo(x)<0)
index = i;
}
K temp = data[index];
while(index<size-1)
{
data[index] = x;
x = temp;
temp = data[index+1];
}
}
size++;
}
// 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.