Heap Sort Stack Over Flow At 100,000 Random Elements

[fonzi]

Hello I am currently working on this code and the code can be runned well from 100-10,000 random elements after that the heap sort says stack over flow, im thinking the recursive calls are the cause of this, so please healp

    public static void MAX_HEAPIFY(int [] A, int i, int n)
    {

        int l = i + 1;//sets the left tree root
        int r = i + 2;//sets the right tree root
        int largest = 0;

        if(l <= n && A[l] > A[i])
        {
            largest = l;
        }
        else
        {
            largest = i;
        }
        if(r <= n && A[r] > A[largest])
        {
            largest = r;
        }
        if(largest != i)
        {
            int temp = A[largest];
            A[largest] = A[i];
            A[i] = temp;
            MAX_HEAPIFY(A, largest, n);
        }
    }
    //this method builds a max heap takes in an array and a int n
    public static void BUILD_MAX_HEAP(int [] A, int n)
    {
        for(int i = (int) Math.floor(n/2); i >= 0; i --)
        {
            //calls the method max_heapify and inputs the Array passed in
            //the i from the for loop
            //and the n passed in as well.
            MAX_HEAPIFY(A, i, n);
        }
    }
    //this method is the heap sort it takes in one array and a lenght 
    public static void HEAPSORT(int [] A, int n)
    {
        BUILD_MAX_HEAP(A, n);
        for(int i = n; i >= 1; i --)
        {
            //exchanges the elements of the arrays.
            int temp = A[0];
            A[0] = A[i];
            A[i] = temp;
            MAX_HEAPIFY(A, 0, i-1);

        }

    }

and here is the error

Exception in thread "main" java.lang.StackOverflowError
    at AllAlgorithms.MAX_HEAPIFY(AllAlgorithms.java:24)
    at AllAlgorithms.MAX_HEAPIFY(AllAlgorithms.java:45)
    at AllAlgorithms.MAX_HEAPIFY(AllAlgorithms.java:45)

[JamesCherrill]

Yes, it's very likely that the heap overflow is caused by an excess of recursion, however I don't think your max recursion depth should increase so fast with array size (shouldn't it scale with log(n)?). Try putting one or more print statements in each of the methods to show what it's doing then run a (small!) test case - you may find a logic error that is causing too many recursive calls.

[fonzi]

Hey James, Thanks for replaying

i figured out later on that the cause of this is that the JVM stack size is too small for such a big array so the problem can be taken care by just increasing the stack size not the heap size :)

thanks for the idea though

[JamesCherrill]

So sorry, my mind must have been somewhere else when I wrote that. When writing about your java.lang.StackOverflowError (!) I was thinking "stack" but typed "heap" for some reason. My mistake.