Heapsort StackOverflow error

Question

I repeatedly get a StackOverflow error at line marked with ** The stack overflows if I try to sort more than 3 numbers but works for arrays of 3 or less, therefore I do not think there is an infinite recursion. Can someone explain to me why line 246 seems to be the source of the stack overflow?

Thanks

    public static void heapSort(double [] a,int node, int index, boolean upcheck){
if(node < 0){

}
else if(node > a.length-index){
}
else if(upcheck){
    if(!testHeap(a,node,(2*node)+1) || !testHeap(a,node,(2*node)+2) ){
            int min = 0;
            if(a[(2*node)+1] > a[(2*node)+2]){
                min = (2*node)+2;
            }
            else{
                min = (2*node)+1;
            }               
            switchHeap(a,node,min);

****************************heapSort(a,(node-1)/2,index,true);*********************
        }
    }


else if(node == (a.length-index-1)/2){
    if((2*node)+1 <= a.length-index){
        if(testHeap(a,node,(2*node)+1)){            
        }
        else{
            heapSort(a,(node-1)/2,index,true);
        }           
        if((2*node)+2 <= a.length-index){
            if(testHeap(a,node,(2*node)+2)){
            }
            else{
            heapSort(a,(node-1)/2,index,true);
            }   
        }
    }
    switchHeap(a,0,a.length-index);
    index++;
    heapSort(a,0,index,false);
}
else{
    if((2*node)+1 <= a.length-index){
        if(testHeap(a,node,(2*node)+1)){            
        }
        else{
            heapSort(a,(node-1)/2,index,true);
        }
        heapSort(a,(2*node)+1,index,false);
        if((2*node)+2 <= a.length-index){
            if(testHeap(a,node,(2*node)+2)){
            }
            else{
            heapSort(a,(node-1)/2,index,true);
            }   
            heapSort(a,(2*node)+2,index,false);
        }
    }
}

}//heapSort - method

you get StackOverflowError when your Stack is full (in your case its due to recursion..). — TheLostMind, Jan 03 '14 at 08:43
Thanks, I understand how it is caused but I cannot find any reason why the code should cause a stackoverflow. The stack (I think) is at most as long as the tree. — Zhv Z, Jan 03 '14 at 19:39

score 0 · Answer 1 · edited May 23 '17 at 12:28

0

You are getting StackOverFlowError due to the recursive call you make in your code. i.e.

 static void heapSort(double [] a,int node, int index, boolean upcheck)

calls itself recursively. You need to make use of break; in this kind of recursive method calls when the work is done

From the documentation,

public class StackOverflowError extends VirtualMachineError

Thrown when a stack overflow occurs because an application recurses too deeply.

Please read this link to know more about the error. The accepted answer explains it all

edited May 23 '17 at 12:28

Community

1
1

answered Jan 03 '14 at 08:48

Keerthivasan

12,760
2
32
53

I thinK I do have a base case in that I check to make sure that the node exists. Do I need something more explicit? Thanks – Zhv Z Jan 03 '14 at 09:10

score 0 · Answer 2 · answered Jan 03 '14 at 09:36

Everytime you call

heapSort(a,(node-1)/2,index,true);

the stack will end up having its own set of variables (double[] , int node, int index...) .. this might be causing the problem if your input size is >3 (too much recursion..).

One solution could be to declare only one array which is to be sorted at instance level, not method level and pass just the indices in your functions instead of passing the array.

this might help - http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html

Thanks for the link, however heapsort is meant to be recursive using arrays right? — Zhv Z, Jan 06 '14 at 03:32

Heapsort StackOverflow error

2 Answers2