Opération BubbleDown sur min-heap binaire ne fonctionne pas

Question

J'essaie d'extraire le minimum d'un tas binaire, mais ça 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 comprends pas pourquoi. J'ai essayé de le 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 peu d'éléments. Vous devez vous arrêter lorsque le plus petit enfant> = élément actuel.

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

L'état du tout ne suffit pas. Il se peut qu'il n'y ait pas de bon enfant mais que vous ayez besoin d'échanger avec l'enfant de gauche. De plus, comme le suggère Henk, vous devez vérifier si le minimum calculé est en fait plus petit que votre valeur actuelle.