Операция BubbleDown для двоичной min-heap не работает

Question

Я пытаюсь извлечь минимум из двоичной кучи, но он не работает. Вот мой код 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;
    }
}

Похоже, что меняются только несколько цифр, но не все, я не могу понять почему Я пытался перекодировать это по-другому и уже много раз ...

Что я делаю не так?

Answer 1

Состояние пока недостаточно. Может случиться так, что правого ребенка нет, но вам нужно поменяться с левым ребенком. Более того, как предлагает Хенк, вам нужно проверить, действительно ли рассчитанный минимум меньше вашего текущего значения.

Answer 2

Не думаю, что проблема в том, что он переходит на несколько элементов. Вы должны остановиться, когда самый маленький ребенок> = текущий элемент.

Я бы переписал последние две строки:

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