operación BubbleDown en binario min-montón no funciona

Question

Estoy intentando extraer el mínimo de un montón binario, pero que no está funcionando. Aquí está mi código BubbleDown:

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

Parece que sólo se intercambia un par de números, pero no todos ellos, no puedo entender por qué. He intentado volver a codificar de manera diferente y muchas veces ya ...

¿Qué estoy haciendo mal?

Answer 1

No creo que el problema es que se intercambia con pocos elementos. Usted tiene que parar cuando el niño más pequeño> = elemento actual.

Me reescribir las dos últimas líneas a:

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

Answer 2

La condición del tiempo no es suficiente. Puede ser el caso que no hay hijo derecho, pero que tiene que hacer el intercambio con el hijo izquierdo. Por otra parte, como sugiere Henk, es necesario comprobar si el mínimo calculado es de hecho menor que su valor actual.