What is wrong with my Heap Sort code in Java?

Question

I'm trying to create and sort a heap using this array in Java. I keep getting an array index out of bounds exception in my maxHeap function. The code seems to make sense to me, so I'm not sure where the error is coming from.

Anyone know what I'm doing wrong?

 public static void main(String[] args) {
    int[] array = { 5, 16, 10, 7, 43, 12, 75, 33, 47, 3, 2489, 591, 6639, 557, 84, 9054, 17, 8841, 99, 701, 21, 78, 9, 36, 839};
    heapSort(array3);
    System.out.println("Heap Sort:");
    printArray(array3);
}

public static void createHeap(int []A){
    int n = A.length-1;
    for(int i=n/2;i>=0;i--){
        maxheap(A,i);
    }
}

public static void maxheap(int[] A, int i){ 
    int n = A.length;
    int largest;
    int left=2*i;
    int right=2*i+1;
    if(left <= n && A[left] > A[i]){
        largest=left;
    }
    else{
        largest=i;
    }

    if(right <= n && A[right] > A[largest]){
        largest=right;
    }
    if(largest!=i){
        int temp=A[i];
        A[i]=A[largest];
        A[largest]=temp;
        maxheap(A, largest);
    }
}

public static void heapSort(int []A){
    createHeap(A);
    int n= A.length;
    for(int i=n;i>0;i--){
        int temp=A[0];
        A[0]=A[i];
        A[i]=temp;
        n=n-1;
        maxheap(A, 0);
    }
}


public static void printArray(int[] sortedArray) {

   for (int i = 0; i < sortedArray.length; i++) {
       System.out.print(sortedArray[i] + ", ");
   }
   System.out.println("");
}

Answer 1

You are declaring int n three times, first time as:

int n = A.length - 1;

in createHeap()

second time:

int n = A.length;

in maxHeap() and third time:

int n = A.length;

in heapSort();

In maxHeap() right is set to 25 and therefor A[right] (A[25]) is out of bounds

You can leave int n = A.length out of both heapSort() and maxHeap().

Answer 2

Arrays in Java are zero-indexed. You're setting your loop upper bound (n) to be A.length, then doing a less than or equal to comparison against it, so it will always check for one too many elements.

if(left <= n && A[left] > A[i]){

Should be

if(left < n && A[left] > A[i]){

And

if(right <= n && A[right] > A[largest]){

Should be

if(right < n && A[right] > A[largest]){

You're also performing a dodgy operation to initialise right. createHeap() sets i to be equal to n/2 (which is potentially a bug in itself). You then pass this value through to maxHeap in the form of the parameter i. Then you're doing this:

int right = 2*i+1;

What happens here when i is say, 2?

In order for i to be 2, A.length must be 5 or 6 (because createHeap sets n to be A.length - 1, so (5 - 1) / 2 = 4 as does (6 - 1) / 2). When this trickles through to maxheap, 2 * i + 1 takes you up to 5, which is out of bounds of A (it may be the length, but if that's the case, then 4 is the highest index, not 5).

So, this is the situation when A.length = 5:

if(right <= n && A[right] > A[largest]) {
   ^ 5      ^ 5    ^ ArrayIndexOutOfBoundsException thrown here.

right <= n evaluates to true, because 5 does indeed equal 5, so A[right] is evaluated, and promptly fails with your exception. A simple less than check on right < n would prevent this, as 5 is not less than 5, so the first condition evaluates to false, thereby ensuring that A[right] would not get evaluated at all.

In short - this doesn't work for an odd length array.

Remember: The .length property of an array tells you how many elements that array can contain, not the index of the last element.