I am trying to create a heap sort method using recursion but whenever one of my methods called maxHeapify is called, it would throw a StackOverflowError. I understand that this error will pop up whenever my application recurses too deeply but the problem is I don't see anything wrong with my maxHeapify method that would cause such an error.

Here's the code:

public class Sorting {
		
	public static void maxHeapify (int[] A, int i) throws OutOfRangeException{
		
		int heapSize = A.length;
		
		if ((i < 0) || (i >= heapSize)){
			throw new OutOfRangeException();
		}
		
		int left = (2*i)+1;
		int right = (2*i)+2;
		int largest = i;
		
		if ((left < heapSize ) && (A > A[i])){
			largest = left;
		}
		
		if ((right < heapSize) && (A > A[i])){
			largest = right;
		}
		
		if (largest != i){
			int tmp = A[i];
			A[i] = A[largest];
			A[largest] = tmp;
		}

		maxHeapify(A, largest);
	}
	
	
	public static void buildHeap (int[] A){
		int n = A.length;
		int i = (int) Math.floor(n/2) - 1;
		
		try{
		while (i > 0){
			maxHeapify(A, i);
			i --;
		}
		}
		catch (OutOfRangeException ex){
			System.out.println("Error: Out of range");
		}
	}
	
	public static int deleteMax (int[] A) throws Exception{
		int heapSize = A.length;
		
		if (heapSize > 1){
			int largest = A[0];
			A[0] = A[heapSize -1];
			heapSize --;
			maxHeapify(A, 0);
			return largest;
		}
		else if (heapSize == 1){
			heapSize = 0;
			return A[0];
		}
		else{
			throw new Exception();
			//throw new EmptyHeapException();
		}
	}
	
	public static void heapSort(int [] A){
		
		int heapSize = A.length;
		
		if (heapSize > 1){
			buildHeap(A);
			int i = heapSize-1;
			
			while (i > 0){
				try{
					A[i] = deleteMax(A);
					i--;
				}
				catch (Exception ex){
					System.out.println("Heap is empty, unable to sort array.");
				}
			}
		}
	}
}

It'll be great if anyone can help me out.

It doesn't seem like your maxHeapify method has a base case. Meaning, even when it finds the values you are looking for, it will keep looking for those values. You need a base case so that once the method finds what its looking for, it no longer continues calling itself. Try adding this:

if (largest != i){
			int tmp = A[i];
			A[i] = A[largest];
			A[largest] = tmp;
}
else{ //putting return here prevents the method from calling itself again
return;
}

Ah, can't believe I missed that... Thanks for all your help. My code's running fine now. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.