Implement the PriorityQ class in the priorityQ.java program (Listing 4.6) using a heap instead of an array. You should be able to use the Heap class in the heap.java program (Listing 12.1) without modification. Make it a descending queue (largest item is removed). Be sure to add an application class to test the class requested. Be sure that the code compiles and executes correctly.

_______________________________________________________________________________________

// priorityQ.java // demonstrates priority queue // to run this program: C>java PriorityQApp //////////////////////////////////////////////////////////////// class PriorityQ

{ // array in sorted order, from max at 0 to min at size-1 private int maxSize; private long[] queArray; private int nItems;

//-------------------------------------------------------------

//-------------------------------------------------------------

public void insert(long item) {

int j;

if(nItems==0) queArray[nItems++] = item;

else {

for(j=nItems-1; j>=0; j--) {

if( item > queArray[j] ) queArray[j+1] = queArray[j]; // shift upward

// insert item

// if no items,

// insert at 0 // if items,

// start at end,

// if new item larger,

Priority Queues 147

public PriorityQ(int s) {

maxSize = s; queArray = new long[maxSize]; nItems = 0; }

// constructor

else break;

} // end for queArray[j+1] = item; nItems++; } // end else (nItems > 0)

// if smaller, // done shifting

// insert it

} // end insert() //-------------------------------------------------------------

public long remove() // remove minimum item { return queArray[--nItems]; }

//------------------------------------------------------------- public long peekMin() // peek at minimum item

{ return queArray[nItems-1]; } //-------------------------------------------------------------

public boolean isEmpty() // true if queue is empty { return (nItems==0); }

//------------------------------------------------------------- public boolean isFull() // true if queue is full

{ return (nItems == maxSize); } //-------------------------------------------------------------

} // end class PriorityQ //////////////////////////////////////////////////////////////// class PriorityQApp

{ public static void main(String[] args) throws IOException

{ PriorityQ thePQ = new PriorityQ(5); thePQ.insert(30); thePQ.insert(50); thePQ.insert(10); thePQ.insert(40); thePQ.insert(20);

while( !thePQ.isEmpty() ) {

long item = thePQ.remove(); System.out.print(item + ); // 10, 20, 30, 40, 50 } // end while

System.out.println();

} // end main() //-------------------------------------------------------------

} // end class PriorityQApp

_____________________________________________________________________________________________

LISTING 12.1 The heap.java Program

// heap.java // demonstrates heaps // to run this program: C>java HeapApp import java.io.*; //////////////////////////////////////////////////////////////// class Node

{

private int iData; // data item (key) // -------------------------------------------------------------

public Node(int key) // constructor

{ iData = key; }

// -------------------------------------------------------------

public int getKey() { return iData; }

// ------------------------------------------------------------- public void setKey(int id)

{ iData = id; }

// -------------------------------------------------------------

} // end class Node //////////////////////////////////////////////////////////////// class Heap

{ private Node[] heapArray; private int maxSize; // size of array private int currentSize; // number of nodes in array

// ------------------------------------------------------------- public Heap(int mx) // constructor

{ maxSize = mx; currentSize = 0; heapArray = new Node[maxSize]; // create array }

// ------------------------------------------------------------- public boolean isEmpty()

{ return currentSize==0; }

// -------------------------------------------------------------

public boolean insert(int key) {

if(currentSize==maxSize) return false;

Node newNode = new Node(key); heapArray[currentSize] = newNode; trickleUp(currentSize++); return true;

} // end insert()

// -------------------------------------------------------------

public void trickleUp(int index) {

int parent = (index-1) / 2; Node bottom = heapArray[index];

while( index > 0 && heapArray[parent].getKey() < bottom.getKey() )

{ heapArray[index] = heapArray[parent]; // move it down index = parent; parent = (parent-1) / 2; } // end while

heapArray[index] = bottom;

} // end trickleUp() // -------------------------------------------------------------

public Node remove() // delete item with max key { // (assumes non-empty list) Node root = heapArray[0]; heapArray[0] = heapArray[--currentSize]; trickleDown(0);

return root;

} // end remove() // -------------------------------------------------------------

public void trickleDown(int index) {

int largerChild; Node top = heapArray[index]; while(index < currentSize/2)

{ int leftChild = 2*index+1; int rightChild = leftChild+1;

if(rightChild < currentSize && heapArray[leftChild].getKey() <

heapArray[rightChild].getKey()) largerChild = rightChild;

else largerChild = leftChild;

// top >= largerChild? if( top.getKey() >= heapArray[largerChild].getKey() )

break;

// shift child up heapArray[index] = heapArray[largerChild]; index = largerChild; // go down

} // end while heapArray[index] = top; // root to index

while( index > 0 && heapArray[parent].getKey() < bottom.getKey() )

{ heapArray[index] = heapArray[parent]; // move it down index = parent; parent = (parent-1) / 2; } // end while

heapArray[index] = bottom;

} // end trickleUp() // -------------------------------------------------------------

public Node remove() // delete item with max key { // (assumes non-empty list) Node root = heapArray[0]; heapArray[0] = heapArray[--currentSize]; trickleDown(0);

return root;

} // end remove() // -------------------------------------------------------------

public void trickleDown(int index) {

int largerChild; Node top = heapArray[index]; while(index < currentSize/2)

{ int leftChild = 2*index+1; int rightChild = leftChild+1;

if(rightChild < currentSize && heapArray[leftChild].getKey() <

heapArray[rightChild].getKey()) largerChild = rightChild;

else largerChild = leftChild;

// top >= largerChild? if( top.getKey() >= heapArray[largerChild].getKey() )

break;

// shift child up heapArray[index] = heapArray[largerChild]; index = largerChild; // go down

} // end while heapArray[index] = top; // root to index

// save root // while node has at // least one child,

// find larger child

// (rightChild exists?)

} // end trickleDown() // -------------------------------------------------------------

public boolean change(int index, int newValue) {

if(index<0 || index>=currentSize) return false;

int oldValue = heapArray[index].getKey(); // remember old

else System.out.print( -- );

System.out.println();

int nBlanks = 32; int itemsPerRow = 1; int column = 0; int j = 0; String dots = ...............................;

// dotted top line

// for each heap item

// first item in row? // preceding blanks

System.out.print( ); System.out.print(heapArray[j].getKey());

System.out.println(dots+dots);

while(currentSize > 0) {

if(column == 0) for(int k=0; k

// heap format

// current item

// display item

heapArray[index].setKey(newValue);

if(oldValue < newValue) trickleUp(index);

if(++j == currentSize)

break;

if(++column==itemsPerRow) {

nBlanks /= 2; itemsPerRow *= 2; column = 0; System.out.println(); }

else for(int k=0; k

System.out.print( ); // } // end for

System.out.println( +dots+dots); //

} // end displayHeap() // -------------------------------------------------------------

} // end class Heap //////////////////////////////////////////////////////////////// class HeapApp

{ public static void main(String[] args) throws IOException

{ int value, value2; Heap theHeap = new Heap(31); // make a Heap; max size 31 boolean success;

theHeap.insert(70); theHeap.insert(40); theHeap.insert(50); theHeap.insert(20); theHeap.insert(60); theHeap.insert(100); theHeap.insert(80); theHeap.insert(30); theHeap.insert(10); theHeap.insert(90);

// insert 10 items

// until [Ctrl]-[C] System.out.print(Enter first letter of );

while(true) {

//

//

// // // //

done?

end of row?

half the blanks twice the items start over on

new row next item on row interim blanks dotted bottom line

else trickleDown(index);

return true;

// change to new

// if raised, // trickle it up // if lowered, // trickle it down

} // end change() // -------------------------------------------------------------

public void displayHeap() {

System.out.print(heapArray: ); // array format for(int m=0; m

if(heapArray[m] != null) System.out.print( heapArray[m].getKey() + );

System.out.print(show, insert, remove, change: ); int choice = getChar(); switch(choice)

{ case s:

theHeap.displayHeap();

value = getInt(); success = theHeap.insert(value); if( !success )

System.out.println(Cant insert; heap full); break;

case r: // remove if( !theHeap.isEmpty() )

theHeap.remove(); else

System.out.println(Cant remove; heap empty); break;

case c: // change System.out.print(Enter current index of item: ); value = getInt(); System.out.print(Enter new key: ); value2 = getInt(); success = theHeap.change(value, value2); if( !success )

System.out.println(Invalid index); break;

default: System.out.println(Invalid entry );

} // end switch } // end while

} // end main() //-------------------------------------------------------------

public static String getString() throws IOException {

InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s;

// show

// insert System.out.print(Enter value to insert: );

break; case i:

} //-------------------------------------------------------------

public static char getChar() throws IOException {

String s = getString(); return s.charAt(0); }

//------------------------------------------------------------- public static int getInt() throws IOException

{ String s = getString(); return Integer.parseInt(s); }

//------------------------------------------------------------- } // end class HeapApp

////////////////////////////////////////////////////////////////