- #1
kmr159
- 7
- 0
Homework Statement
Develop a Heapsort algorithm using java
Homework Equations
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:
public static void heapSort(double [] a, int node, int index){
System.out.println("made it");
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: