Solving Heapsort in Java: Understanding Index Values

[kmr159]

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

	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

 

[.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?

 

[.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)

 

[jedishrfu]

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.