0

配列データ構造を使用して最小ヒープの実装に取り​​組んでいますが、moveDown メソッドに問題があります (ルート ノードで使用され、ルートの子がそれよりも小さい場合にコレクションをヒープに戻します)。読者は最小ヒープとは何かを知っていると思いますが、知らない人や私の理解が間違っている場合に備えて説明します。

最小ヒープ (この場合) は、次のような配列で表されるバイナリ ツリーです。

  1. ルート ノードは、データ構造の最小値です。
  2. ノードは常にその子よりも小さくする必要があります
  3. 配列インデックス I のノードを指定すると、左側の子はインデックス I*2 + 1 になり、右側の子は I*2 + 2 になります。

私が抱えている現在の問題は、スワッピング時に moveDown 関数が無限ループに陥ることです。論理エラーを見つけるのに非常に苦労しているので、根本に近いものかもしれないのではないかと心配しています (しゃれが意図されていて、私は自分自身を助けることができませんでした)。

heap.cpp ファイルの注目すべきデータ メンバー:

int size;
MiniVector array;// The implementing custom array
void moveDown(int root);

私の heap.cpp ファイルの moveDown 関数:

void BinaryHeap::moveDown( int root ){

    int temp = root;
    int tempLC = temp*2 + 1;//LeftChild
    int tempRC = temp*2 + 2;//RightChild

    //Not a leaf
    while( ( tempLC < array.size() && tempRC < array.size() )
        &&
    ( (array[temp] > array[tempLC]) || (array[temp] > array[tempRC]) ) ){

        int hold = array[temp];

        if( array[temp] > array[tempRC] ){

            array[temp] = array[tempRC];
            array[tempRC] = hold;
            temp = tempRC;
        }

        else{

            array[temp] = array[tempLC];
            array[tempLC] = hold;
            temp = tempLC;
        }

        int tempLC = temp*2 + 1;//LeftChild
        int tempRC = temp*2 + 2;//RightChild
    }
}
4

1 に答える 1

1

変数を再宣言します。while ループの一番下

    int tempLC = temp*2 + 1;//LeftChild
    int tempRC = temp*2 + 2;//RightChild

する必要があります

    tempLC = temp*2 + 1;//LeftChild
    tempRC = temp*2 + 2;//RightChild

Javaでは起こりません。

また、ループを途中で中断して無限 for ループとして書き直した場合も発生しません。

for (;;)
{
    int tempLC = temp*2 + 1;//LeftChild
    int tempRC = temp*2 + 2;//RightChild
    if (...)
        break;
    ...
}

しかし、この種のループが良いアイデアだと提案するたびに、私は激怒します。前回、それは「ほぼアンチパターン」であると示唆した人もいましたが、それはより丁寧な回答の 1 つです。

于 2013-04-08T20:54:06.907 に答える