2 
void ReheapDown( int* heap, int top, int swpIndx, int numElements )  {
    int leftChild = 2 * top + 1;
    int rightChild = 2 * top + 2;
    int minChild;
    if (leftChild < numElements) {
        // find subscript of smallest child
        if (rightChild >= swpIndx || heap[leftChild] < heap[rightChild])
            minChild = leftChild;
        else
            minChild = rightChild;
        // if data at top is greater than smallest
        // child then swap and continue
        if (heap[top] > heap[minChild]) {
            swap( heap[top], heap[minChild] );
            ReheapDown( heap, minChild, swpIndx, numElements );
        }
    }

これは単純なヒープ用です。ReheapDownは、ヒープ内のアイテムを削除するために部分的に使用されます。しかし、何をしswpIndxますか？（私は宿題をすることを知る必要があります。そこでは、ヒープ内の特定のキーを削除する関数を作成することになっています。）

4

1 に答える 1

1

ヒープからキーを削除するには、キーを削除する前に、ヒープ内の最後のキーと交換することをお勧めします。そうしないと、ヒープにギャップのある穴ができてしまいます。

ただし、最後のノードを削除するノードと交換すると、ヒープの順序が乱れる可能性があります。これは、指定したReheapDownメソッドの出番です。

swpIndexパラメーターは、削除したい要素を配置したインデックスだと思います。したがって、コードのその部分は基本的に次のようになります。

if (there exists a left child) {
    if (there is no right child || left child < right child)
        minChild <- left child
    else
        minChild <- right child
}

ただし、左右の子の存在を確認することが唯一の目的のようですので、パラメータは不要だと思います。これは、leftChildおよびrightChildインデックスをnumElementsと比較することによっても実現できます。

お役に立てれば ：）

于 2012-06-09T23:12:39.153 に答える