# Homework Help: HeapSort Java

1. Jan 6, 2014

### kmr159

1. The problem statement, all variables and given/known data
Develop a Heapsort algorithm using java

2. Relevant equations

3. The attempt at a solution

I have been trying to implement HeapSort in java. Unfortunately I am running into errors. I am printing out the index values and they go up then down and the code does not sort properly. Can you help me understand why the index values decease. Thanks.

This comment explains how I find the final node before switching the values

// log base 2 of (a.length - index) - truncating to get the int value - gives the length of the tree. 2^(treelength) - 1 gives the position of the final node that will be evaluated before the top value is swapped with the bottom value

The full code is here or below

http://pastebin.com/7tvTc4Nb

Code (Text):

public static void heapSort(double [] a, int node, int index){
int finalnode = 0;
int treelength = 0;
treelength = (int)((Math.log(a.length-index))/(Math.log(2)));

finalnode = Math.pow(2,treelength) - 1;// log base 2 of (a.length - index) - truncating to get the int value - gives the length of the tree. 2^(treelength) - 1 gives the position of the final node that will be evaluated before the top value is swapped with the bottom value

System.out.println("THe Finalnode is " + finalnode);
System.out.println("The index is " + index);
if(!(node > finalnode-1) && node >= 0 && index < a.length){
System.out.println("in");
boolean switchval = false;
double holder = 0;

if(node == finalnode){
switchval = true;
}
if(minNode(a,node,index) != -1){
fixHeap(a,node, index);
}
if(switchval){
System.out.println("Switch");
holder = a[0];
a[0] = a[a.length-(1+index)];
a[a.length-(1+index)] = holder;
index++;
heapSort(a,0,index);
}
else{
heapSort(a,(2*node) +1,index);
heapSort(a,(2*node) +2,index);
}
}
}//heapSort

public static int minNode(double [] a, int node,int index){
double min;
int pos;
if((2*node + 1) < a.length - index){
if((2*node + 2) < a.length - index){
if(a[(2*node + 1)] > a[(2*node + 2)]){
min = a[(2*node + 2)];
pos = (2*node + 2);
}
else{
min = a[(2*node + 1)];
pos = (2*node + 1);

}

if(a[node] < min){
return (-1);
}
else{
return pos;
}

}// if 2nd child exists
min = a[(2*node + 1)];
pos = (2*node + 1);
if(a[node] < min){
return (-1);
}
else{
return pos;
}
}// if 1st child exists
return -1;
}//testNode

public static void fixHeap(double [] a, int node, int index){
int test = node;
int minNode = 0;
double holder;
int counter = 0;
while(true){

counter++;
if(test >= 0){
minNode = (minNode(a,test, index));
if(minNode == -1){
break;
}
holder = a[test];
a[test] = a[minNode];
a[minNode] = holder;
test = (test-1)/2;
}
else{
break;
}
}
}//fixHeap

Last edited by a moderator: Jan 6, 2014
2. Jan 8, 2014

### .Scott

My suggestion for debugging this is to take a small example (say an array of 8 unsorted values) and work out exactly what you expect to be done by hand.
Then put a break point in the two places code where "holder" is set and see exactly what is happening.

On a quick look at your code, the only thing that alarmed me was the computation of treelength. Let's say that (a.length-index) is 8. What would keep treelength from being (int)2.999999999?

3. Jan 9, 2014

### .Scott

Also, I'm guessing that you enter this routine with this call:
heapSort(a, 0, 0)

I would suggest renaming heapSort to nodeSort and then creating a new heapSort with this interface:

public static void heapSort(double [] a)

4. Jan 9, 2014

### Staff: Mentor

Do you have an IDE like eclipse or netbeans? They provide an interactive debugger that can walk you thru the code line by line and you can inspect the value of your variables... It's definitely something to spend some time as it will improve your programming skill and will be useful in the future.

I use netbeans extensively at work and the debugger is just indispensable.

Have you looked at other heap sort implementations on the web? Reviewing them might elicit what is happening in your code.