The heap java Program heap java demonstrates heaps to run this program c java HeapApp import java

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

LISTING 12.1 Continued

{ iData = key; }

• //  -------------------------------------------------------------

public int getKey() { return iData; }

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

{ iData = id; }

• //  -------------------------------------------------------------

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

Java Code for Heaps 593

{ private private private

Node[] heapArray;
int maxSize; // size of array
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];

594 CHAPTER 12 Heaps

LISTING 12.1 Continued

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

LISTING 12.1 Continued

} // 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<nBlanks; k++)

// heap format

// current item

// display item

Java Code for Heaps 595

heapArray[index].setKey(newValue);

if(oldValue < newValue) trickleUp(index);

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<currentSize; m++)

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

596 CHAPTER 12 Heaps

LISTING 12.1 Continued if(++j == currentSize)

break;

if(++column==itemsPerRow) {

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

else
for(int k=0; k<nBlanks*2-2; k++)

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

System.out.println(“n”+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

//

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme