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.

 

[rezeew]

Hello, thank you for sharing your code and the explanation of your thought process. It seems like you are on the right track with your HeapSort implementation in Java. However, there are a few things that could be causing the errors you are experiencing.

Firstly, it's important to note that in your code, you are using a "min heap" instead of a "max heap". This means that the smallest value will be at the root of the heap, and the larger values will be towards the bottom. If you are trying to sort in ascending order, this is not a problem. However, if you are trying to sort in descending order, you will need to make some changes to your code.

Secondly, your code seems to be using a recursive approach, which can be more difficult to debug and understand. It might be helpful to try implementing a non-recursive approach, using a loop instead. This will also help you avoid potential stack overflow errors.

Additionally, it's important to make sure that your code is correctly handling edge cases, such as when the array is empty or has only one element. It's also important to make sure that your code is correctly handling the case where the index value is equal to the length of the array, as this could cause unexpected results.

I recommend that you carefully review your code and consider these suggestions. You may also want to use a debugger or add print statements to help you identify where the errors are occurring. Good luck with your HeapSort implementation!