{
private K data[];
private int size;
private int capacity;
// constructors
public MaxHeapPQ()
{
capacity = 100;
size = 0;
data = (K[]) new Comparable[capacity];
}
public MaxHeapPQ(int c)
{
capacity = c;
size = 0;
data = (K[]) new Comparable[capacity];
}
// required priority queue methods
public boolean isEmpty(){
//ADD CODE
}
public void add(K x) throws Exception {
//ADD CODE
}
public K removeMax() throws Exception {
if (size <= 0)="" throw="" new="" exception("priority="" queue="">
//ADD CODE
}
// 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 <=>
return;// at root
K dn = data[n];
K dp = data[(n - 1) / 2]; // parent data
//ADD CODE
}
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;
//ADD CODE
}
// 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");
}
/* Add a min() method to find the minimum. Your implementation should use constant time and constant extra space. * Hint: add an extra instance variable that points to the minimum item. Update it after each call to add(K x). * Return null if the heap is empty. */
public K min(){
//ADD CODE
}
public static void main(String[] args){
MaxHeapPQ heap = new MaxHeapPQ();
try{
heap.add("q");
heap.add("w");
heap.add("e");
heap.add("r");
heap.add("t");
heap.add("y");
System.out.println(heap.min()); // the output would be e
while (!heap.isEmpty()) System.out.print(heap.removeMax()); // the printout would be ywtrqe
System.out.println();
}
catch (Exception e){
System.out.println("Error " + e.toString());
}
}
}
interface MaxPriorityQueue> {
public void add(K x) throws Exception;
public K removeMax() throws Exception;
public boolean isEmpty();
}