HeapSort Code snipplet giving Index Out of bound exception

Question

I am trying the following code for heap sort which is giving ArrayIndexOutOfBoundsException exception:

package com.Sorting;

import java.util.Arrays;

public class HeapSort {

    private static int arr[];
    private static int l,r,max,hsize;
    /**
     * @param args
     */
    public static void main(String[] args) {
        int []numbers={55,2,93,1,23,10,66,12,7,54,3};
          System.out.println(Arrays.toString(numbers));
          HeapSort(numbers);
          System.out.println(Arrays.toString(numbers));
    }

    private static void HeapSort(int myarr[]) {
        // TODO Auto-generated method stub
        arr = myarr;
         hsize = arr.length - 1;
        BuildHeap(arr);
        for(int i = hsize;i>0;i--)
        {
            swap(0,i);
            hsize--;
            SatisfyHeap(arr,0);
        }       
        }

    private static void BuildHeap(int[] arr) {
        // TODO Auto-generated method stub
        for(int i = hsize/2; i>=0;i--)
        {
            SatisfyHeap(arr, i);

        }
    }

    private static void SatisfyHeap(int[] arr, int i) {
        // TODO Auto-generated method stub
         l = 2*i;
         r = 2*i+1;
        if(l<=hsize && arr[l]>arr[i])
    //  if(arr[l]>arr[i] && l<=hsize  )
        {
            max = l;
        }
        else
            max = i;
        if(r<=hsize && arr[r]>arr[max])
        {
            max = r;
        }

        if(max!=i)
        {
            swap(i,max);
            SatisfyHeap(arr, max);
        }

    }

    private static void swap(int i, int max) {
        // TODO Auto-generated method stub
        int temp = arr[i];
        arr[i] = arr[max];
        arr[max] = temp;    
    }
}

The above code does not give any error if I just swap the expressions used on the left hand side and right hand side in the if statement of SatisfyHeap method. i.e. you can try commenting the third line of the SatisfyHeap method and uncomment the fourth line. Please help to understand this magic.

Answer 1

Short answer

The magic is called "short-circuit evaluation" and it was designed speciifcally for the cases like this.

Longer answer

In Java and many other languages logicallly code

if (condition1 && condition2) { 
    do something 
}

is equivalent to

if (condition1) {
    if (condition2) { 
        do something 
    }
}

By "equivalent" here I mean that if condition2 is something to be computed it will not be computed if condition1 happens to be false. Also this is correct from the boolean logic point of view. This trick is useful in two respects. First, it improves performance by skipping evaluation calculation2. Secondly, it is useful in cases such as yours were condition1 is a "guard condition" for condition2.

Another example is function isEmptyString that is implemented by many Java-developers in a following way

public static boolean isEmptyString(String s) {
    return (string == null) || (string.length() == 0);
}

Without short-circuting logic, this expression would raise a NullPointerException if s happens to be null.

Your specific case (Why ArrayIndexOutOfBoundsException at all?)

Another point of your question might be "How it happens that there is ArrayIndexOutOfBoundsException at all?". To answer this question consider the case when the very first element is actually the largest in the heap and we should move it down to the last layer of the tree. This movement down is implemented by your SatisfyHeap. So now assume that we did last swap that moved the biggest element to the bottom. Now as max was changed we'll do one more recursive call and in that call i > arr.length / 2 so l = 2*i > arr.length and thus the exception happens.

Side-note, I'd say that unless you pre-allocate arr to be bigger than actual heap size storing hsize independently from arr.length is a bad idea that makes code harder to understand.