1

バイナリ ヒープから最小値を抽出しようとしていますが、うまくいきません。ここに私の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;
    }
}

いくつかの数字だけを交換しているように見えますが、すべてではありません。理由がわかりません。私はそれを別の方法で再コーディングしようとしましたが、すでに何度も...

私は何を間違っていますか？

4

2 に答える 2

2

しばらくの間の状態が十分ではありません。右の子がいない場合は、左の子と交換する必要があります。さらに、ヘンクが示唆するように、計算された最小値が実際に現在の値よりも小さいかどうかを確認する必要があります。

于 2010-04-21T16:32:23.440 に答える
2

問題は、いくつかの要素にスワップすることではないと思います。最小の子>=現在のアイテムになったら停止する必要があります。

最後の 2 行を次のように書き換えます。

    if (heap->items[idx] > heap->items[min]) {
       heapSwapValue(&(heap->items[idx]), &(heap->items[min]));
       idx = min;
    } 
    else
       break;
}
于 2010-04-21T16:23:54.747 に答える