opération BubbleDown sur min tas binaire ne fonctionne pas

Question

Je suis en train d'extraire le minimum d'un tas binaire, mais il ne fonctionne pas. Voici mon code 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;
    }
}

On dirait qu'il permute seulement quelques chiffres, mais pas tous, je ne peux pas comprendre pourquoi. J'ai essayé de recoder différemment et plusieurs fois déjà ...

Qu'est-ce que je fais mal?

Answer 1

Je ne pense pas que le problème est qu'il permute à quelques éléments. Vous devez arrêter quand le plus petit enfant> = item courant.

Je réécrire les deux dernières lignes:

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

Answer 2

La condition du tout ne suffit pas. Il peut être le cas qu'il n'y a pas d'enfant, mais juste que vous devez faire l'échange avec l'enfant gauche. De plus, comme Henk suggère, vous devez vérifier si le minimum calculé est en fait plus petit que votre valeur actuelle.