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.