I am getting Exception in thread "main" java.lang.nullpointerException on line 113,92,200, need help
// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
import java.io.*;
//
//import java.util.Scanner;
class Node
{
private int iData; // data item (key)
// ------------------------------------------------------------
public Node(int key) // constructor
{
iData = key;
System.out.println(" I am in costructor Node " + iData);
}
// ------------------------------------
public int getKey()
{
//System.out.println(" I am in getkey");
return iData;
}
// ------------------------------------------------------------
public void setKey(int id)
{
System.out.println(" I am in setKey");
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;
currentSize = 0;
heapArray = new Node[maxSize]; // create array
}
// ------------------------------------------------------------
public boolean isEmpty() // if heap(array) is empty there os 0 element
{ return currentSize==0; }
// ------------------------------------------------------------
public boolean insert(int key)
{
if(currentSize==maxSize) // heap is full, can't insert
return false;
Node newNode = new Node(key);
System.out.println("newNode = " + newNode.getKey() + "CurrentSize = " + currentSize ); //+ " Node(key) = " + Node(key)); // Remove later
heapArray[currentSize] = newNode;
//System.out.println(" heapArray[currentSize] = " + heapArray[currentSize] ); //Remove
perculateUp(currentSize++); // point to next empty array location
return true;
} // end insert()
// ------------------------------------------------------------
public void perculateUp(int index)
{
System.out.println(" currentSize++ = " + currentSize);
int parent = (index-1) / 2;
//int parent = (index) / 2;
System.out.println("index = " + index + " parent = " + parent);
Node bottom = heapArray[index];
System.out.println("bottom = " + bottom);
System.out.println(" bottom.getkey = " + bottom.getKey() + " heapArray[parent].getKey() = " + + heapArray[parent].getKey() );
while( index > 0 && heapArray[parent].getKey() > bottom.getKey() )
{
System.out.println(" I am in while = "); //remove
heapArray[index] = heapArray[parent]; // move it down
System.out.println(" heapArray[index] before = " + heapArray[index].getKey() );
index = parent;
parent = (parent-1) / 2;
//parent = (parent) / 2;
} // end while
heapArray[index] = bottom;
System.out.println(" heapArray[index] after = " + heapArray[index].getKey() ); //remove
} // end trickleUp()
// ------------------------------------------------------------
public Node remove() // delete item with min key
{ // (assumes non-empty list)
Node root = heapArray[0];
System.out.println(" root = " + root.getKey());
heapArray[0] = heapArray[currentSize]; //heapArray[0] = heapArray[--currentSize];
System.out.println(" heapArray[--currentSize]= " + heapArray[--currentSize].getKey());
perculateDown(0);
return root;
} // end remove()
// ------------------------------------------------------------
public void perculateDown(int index)
{
int smallerChild;
Node top = heapArray[index]; // save root
while(index < currentSize/2) // while node has at
{ // least one child,
System.out.println(" index= " + index);
int leftChild = 2*index+1;
int rightChild = leftChild+1;
System.out.println(" currentSize = " + currentSize + " leftChild = " + leftChild ); // find smaller child
if(rightChild < currentSize && // Is there a right child?
(heapArray[leftChild].getKey() <=
heapArray[rightChild].getKey()))
smallerChild = leftChild; // left child is the smaller child
else
smallerChild = rightChild; // right child is the smaller child
// is top <= smallerChild?
if( top.getKey() <= heapArray[smallerChild].getKey() )
break;
// move smaller child up
heapArray[index] = heapArray[smallerChild];
index = smallerChild; // go down one node
} // end while
heapArray[index] = top; // root to index
} // end perculateDown()
// ------------------------------------------------------------
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() + " ");
else
System.out.print(" -- ");
System.out.println(); // heap format
int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0; // current item
String dots = "...............................";
System.out.println(dots+dots); // dotted top line
while(currentSize > 0) // for each heap item
{
if(column == 0) // first item in row?
for(int k=0; k<nBlanks; k++) // preceding blanks
System.out.print(' ');
// display item
System.out.print(heapArray[j].getKey());
if(++j == currentSize) // done?
break;
if(++column==itemsPerRow) // end of row?
{
nBlanks /= 2; // half the blanks
itemsPerRow *= 2; // twice the items
column = 0; // start over on
System.out.println(); // new row
} // end if
else // next item on row
for(int k=0; k<nBlanks*2-2; k++)
System.out.print(" "); // interim blanks
//System.out.print(' ');
} // end while
System.out.println("\n"+dots+dots); // dotted bottom line
} // 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(31); // insert 10 items
theHeap.insert(16);
theHeap.insert(24);
theHeap.insert(21);
theHeap.insert(13);
//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 element 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;
default:
System.out.println("Invalid entry\n");
} // 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;
}
//------------------------------------------------------------
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