0

The following is a recursive heapify function for an array based priority queue/binary heap.

Can anybody tell me why I'm going into an infinite recursion?

private static void heapify(int i){

    if(i < b_heap.size()/2){

        int left = i * 2;
        int right = left++;

        if(b_heap.get(i).getP() > b_heap.get(left).getP()){
            swap(i,left);
        }
        if(b_heap.get(i).getP() > b_heap.get(right).getP()){
            swap(i,right);
        }

        heapify(i++);
        heapify(i+2);
    }
    else{
        return;
    }
}

ok so I fixed the infinite loop, but the function still doesn't heapify correctly.

here is the new code,

private static void heapify(int i){
    DecimalFormat df = new DecimalFormat("0.00");
    if(i < b_heap.size()/2){
        int left = i * 2;
        int right = i * 2 +1;

        if(b_heap.get(i).getP() > b_heap.get(left).getP()){
            swap(i,left);
        }
        if(b_heap.get(i).getP() > b_heap.get(right).getP()){
            swap(i,right);
        }
        i++;
        heapify(i);
    }
    else{
        return;
    }
}
6
  • I'm not really sure what the i parameter does but if it's given a value, the left and right local variables are always the same value since left++ is evaluated after being assigned to right. Similar thing is happening with heapify(i++) where the increment is evaluated after the call. Following these series of events, infinite recursion happens. Commented Apr 7, 2015 at 20:12
  • So the most useful thing you can do at this point is add a ton of print statements or walk through it in some kind of IDE. I tend towards the print statements initially so I can spot if anything extremely obvious is happening, then start walking my code if nothing looks to suspect. I'd: print i and b_heap.size() before the if print i and b_heap.size() inside the if print i and left in the second if print i and right in the third if print i before the return Commented Apr 7, 2015 at 20:13
  • 1
    You call heapify with i++: this gives heapify i and then increments it.
    – user2030052
    Commented Apr 7, 2015 at 20:20
  • And also you do left++. I think you need to read up on what the ++ operator does. It is NOT the same thing as +1.
    – Sneftel
    Commented Apr 7, 2015 at 20:23
  • Thanks everybody. The error was the i++, I got it to recurse correctly. However the heap it produces is still wrong. did I implement the switches correctly for a min heap? Commented Apr 7, 2015 at 20:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.