--------------------------------------------------------------------------------
ID: 3839512 • 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 check the code in your computer and only give the java code that runs please . thankyou :)
Explanation / Answer
Here's the implementation (replaced TODOs with code):
Sample Output:
Program by: xxxx ---- cmds are + - Q: >>
sh-4.3$ java HelloWorld
Program by: xxxx ---- cmds are + - Q: >>
+
Hello
Program by: xxxx ---- cmds are + - Q: >>
+
World
Program by: xxxx ---- cmds are + - Q: >>
+
Java
Program by: xxxx ---- cmds are + - Q: >>
-
Hello Hello Hello
Program by: xxxx ---- cmds are + - Q: >>
-
Java Java Java
Program by: xxxx ---- cmds are + - Q: >>
-
World World World
Program by: xxxx ---- cmds are + - Q: >>
-
Error java.lang.Exception: Priority Queue Empty
Program by: xxxx ---- cmds are + - Q: >>
Q
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.