In JAVA

I am using Data Structure and algorithms in Java Second Edition

Program Must Compile and run Please WRITE UNDER ONE FILE!

Convert the heap.java program (Listing 12.1) so the heap is an ascending, rather than a descending, heap. (That is, the node at the root is the smallest rather than the largest.) Make sure all operations work correctly.

MUST COMPILE AND RUN ,PLEASE DISPLAY OUTPUT.

Please include main method below with program also sample output below please include screen shots.

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); // insert 10 items

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);

while(true) // until [Ctrl]-[C]

{

System.out.print("Enter first letter of ");

System.out.print("show, insert, remove, change: ");

int choice = getChar();

switch(choice)

{

case 's': // show

theHeap.displayHeap();

break;

case 'i': // insert

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

value = getInt();

success = theHeap.insert(value);

if( !success )

System.out.println("Can't insert; heap full");

break;

case 'r': // remove

if( !theHeap.isEmpty() )

theHeap.remove();

else

System.out.println("Can't remove; heap empty");

break;

case 'c': // change

System.out.print("Enter index of item: ");

value = getInt();

System.out.print("Enter new priority: ");

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()

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 592 CHAPTER 12 Heaps { 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]; // save root while(index < currentSize/2) // while node has at { // least one child, int leftChild = 2*index+1; int rightChild = leftChild+1; // find larger child if(rightChild < currentSize && // (rightChild exists?) 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 } // end trickleDown() // ------------------------------------------------------------- public boolean change(int index, int newValue) { if(index<0 || index>=currentSize) return false; int oldValue = heapArray[index].getKey(); // remember old heapArray[index].setKey(newValue); // change to new if(oldValue < newValue) // if raised, trickleUp(index); // trickle it up else // if lowered, trickleDown(index); // trickle it down return true; } // end change() // ------------------------------------------------------------- public void displayHeap() { System.out.print(heapArray: ); // array format for(int m=0; m 0) // for each heap item { if(column == 0) // first item in row? for(int k=0; k

Output may look like:

Enter first letter of show, insert, remove, change: s

heapArray: 10 20 50 30 60 100 80 70 40 90

..............................................................

10

20 50

30 60 100 80

70 40 90

..............................................................

Enter first letter of show, insert, remove, change: i

Enter value to insert: 5

Enter first letter of show, insert, remove, change: s

heapArray: 5 10 50 30 20 100 80 70 40 90 60

..............................................................

5

10 50

30 20 100 80

70 40 90 60

..............................................................

Enter first letter of show, insert, remove, change: r

Enter first letter of show, insert, remove, change: s

heapArray: 10 20 50 30 60 100 80 70 40 90

..............................................................

10

20 50

30 60 100 80

70 40 90

..............................................................

Enter first letter of show, insert, remove, change: c

Enter index of item: 5

Enter new priority: 45

Enter first letter of show, insert, remove, change: s

heapArray: 10 20 45 30 60 50 80 70 40 90

..............................................................

10

20 45

30 60 50 80

70 40 90

..............................................................

Enter first letter of show, insert, remove, change: