BubbleDown operation on binary min-heap does not work

Question

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;
}