would yo please provide help?

[Totti]

Hi all, i have written a code of a 'MINIMUM' Heap the code seems
working properly in some case, but not in all, i was trying to find
out why, but with no success,
it brings out wrong results for some cases, and the removing method is
not working at all, instead of removing properly, it treats the heap
as a 'MAXIMUM' heap and the result is as if it were a Max heap.
another problem is in changing some values of the numbers, so when
some are changed the whole thing screws up.
would somebody please see the code and tell me what is wrong with it
in general, and especially with the remove method?or is it in the
trickleUp or trickleDown?
any help appreciated

here is the code
//
**************************************************************************
class Heap
{
private Node[] arr;
private int maxSize;
private int nNodes;
// -------------------------------------------------------------
public Heap(int size) // constructor
{
maxSize = size;
nNodes = 0;
arr = new Node[maxSize]; // create array
}
// -------------------------------------------------------------
public boolean isEmpty()
{
return (nNodes == 0);
}
// -------------------------------------------------------------
public boolean insert(int key)
{
if(nNodes == maxSize)
return false;
Node newNode = new Node(key);
arr[nNodes] = newNode;
trickleUp(nNodes);
nNodes++;
return true;
} // end insert()
// -------------------------------------------------------------
public void trickleUp(int index)
{
int parent = (index - 1) / 2;
Node bottom = arr[index];

while( index > 0 && arr[parent].getKey() > bottom.getKey() )
{
arr[index] = arr[parent];
index = parent;
parent = (parent-1) / 2;
}
arr[index] = bottom;
}
// -------------------------------------------------------------
public Node remove()
{
Node root = arr[0];
nNodes--;
arr[0] = arr[nNodes];
trickleUp(0);
return root;
}
// -------------------------------------------------------------
public void trickleDown(int index)
{
int largerChild;
Node top = arr[index];
while(index < nNodes/2)
{
int leftChild = 2*index+1;
int rightChild = leftChild+1;

if(rightChild > nNodes &&
arr[leftChild].getKey() >
arr[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;

if( top.getKey() >= arr[largerChild].getKey() )
break;

arr[index] = arr[largerChild];
index = largerChild;
}
arr[index] = top;
}
// -------------------------------------------------------------
public boolean change(int index, int newValue)
{
if(index<0 || index>=nNodes)
return false;
int oldValue = arr[index].getKey();
arr[index].setKey(newValue);

if(oldValue > newValue)
trickleUp(index);
else
trickleDown(index);
return true;
}
// -------------------------------------------------------------
public void displayHeap()
{
for(int m=0; m<nNodes; m++)
if(arr[m] != null)
System.out.print( arr[m].getKey() + " ");
else
System.out.print( "-- ");
System.out.println();

int nBlanks = 32;
int itemsPerRow = 1;
int column = 0;
int j = 0;
String dots = "...............................";
System.out.println(dots+dots);

while(nNodes > 0)
{
if(column == 0)
for(int k=0; k<nBlanks; k++)
System.out.print(' ');

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

if(++j == nNodes)
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(' ');
}
System.out.println("\n"+dots+dots);
}
}
//*****************************************************************
The method for running the code is in another file, i ll provide it
here, in case it is needed to try the code out :
//****************************************************************
import java.io.*;

class HeapApp
{
public static void main(String[] args) throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String sel;

System.out.println("Enter size of heap:");
sel = br.readLine();
int size = Integer.parseInt(sel);
Heap theHeap = new Heap(size);

int value, value2;


while(true)
{
System.out.print("Enter first letter of show, ");
System.out.print("insert, remove, or change: ");
sel = br.readLine();
char choice = sel.charAt(0);
switch(choice)
{
case 's':
theHeap.displayHeap();
break;

case 'i':
System.out.print("Enter value to insert: ");
sel = br.readLine();
value = Integer.parseInt(sel);
boolean success= theHeap.insert(value);
if (!success)
System.out.println("Can't insert; heap full");
break;


case 'r':
if( !theHeap.isEmpty() )
theHeap.remove();
else
System.out.println("Can't remove; heap empty");
break;

case 'c':
System.out.print("Enter current index of item: ");
sel = br.readLine();
value = Integer.parseInt(sel);
System.out.print("Enter new key: ");
sel = br.readLine();
value2 = Integer.parseInt(sel);
success = theHeap.change(value, value2);
if( !success )
System.out.println("Invalid index");
break;

default:
System.out.print("Invalid entry\n");
}
}
}
}

 

[Patricia Shanahan]

Hi all, i have written a code of a 'MINIMUM' Heap the code seems
working properly in some case, but not in all, i was trying to find
out why, but with no success,
it brings out wrong results for some cases, and the removing method is
not working at all, instead of removing properly, it treats the heap
as a 'MAXIMUM' heap and the result is as if it were a Max heap.
another problem is in changing some values of the numbers, so when
some are changed the whole thing screws up.
would somebody please see the code and tell me what is wrong with it
in general, and especially with the remove method?or is it in the
trickleUp or trickleDown?
any help appreciated

....

I have written up an approach to debug that works for me:
http://home.earthlink.net/~patricia_shanahan/debug/


Patricia