operazione BubbleDown sul binario min-heap non funziona

Question

Sto cercando di estrarre il minimo da un mucchio binario, ma non funziona. Ecco il mio codice 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;
    }
}

Sembra che scambia solo pochi numeri, ma non tutti, non riesco a capire perché. Ho cercato di ricodificare in modo diverso e molte volte già ...

Che cosa sto facendo di sbagliato?

Answer 1

Non credo che il problema è che si scambia a pochi elementi. Devi smettere quando il più piccolo bambino> = item corrente.

vorrei riscrivere le ultime due righe a:

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

Answer 2

La condizione della, mentre non è sufficiente. Può essere il caso che non v'è alcun figlio destro, ma è necessario fare lo scambio con il bambino a sinistra. Inoltre come suggerisce Henk, è necessario controllare se la minima calcolata è di fatto più piccolo della tua valore corrente.