BubbleDown operation on binary min-heap does not work...

Question

Hi,

I'm trying to extract the minimum from a binary heap but it's not working. Here's my BubbleDown code:

void heapBubbleDown(Heap * const heap, int idx) {
    int min;

    while(RIGHT(idx) < heap->count) {
        min = LEFT(idx);

        if(RIGHT(idx) < heap->count) {
            if(heap->items[LEFT(idx)] > heap->items[RIGHT(idx)]) {
                min = RIGHT(idx);
            }
        }

        heapSwapValue(&(heap->items[idx]), &(heap->items[min]));

        idx = min;
    }
}

It looks like it only swaps a few numbers but not all of them, I can't understand why. I tried to recode it differently and many times already...

What am I doing wrong?

Answer 1

I don't think the problem is that it swaps to few elements. You have to stop when the smallest child >= current item.

I would rewrite the last two lines to:

    if (heap->items[idx] > heap->items[min]) {
       heapSwapValue(&(heap->items[idx]), &(heap->items[min]));
       idx = min;
    } 
    else
       break;
}

Answer 2

The condition of the while is not sufficient. It may be the case that there is no right child but you need to do the swap with the left child. Moreover as Henk suggests, you need to check if the calculated minimum is in fact smaller than your current value.