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

//

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. 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. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of