5

次のプログラミングの質問に答えようとしています。

heap.java プログラムでは、このinsert()メソッドによって新しいノードがヒープに挿入され、ヒープの状態が確実に保持されます。toss()ヒープ状態を維持しようとせずにヒープ配列に新しいノードを配置するメソッドを作成します。(おそらく、それぞれの新しい項目を単純に配列の末尾に配置できます。)次にrestoreHeap()、ヒープ全体にわたってヒープ状態を復元するメソッドを記述します。一度に大量のデータを挿入する必要がある場合は、repeatedを使用toss()してから single を使用する方が、 restoreHeap()repeatly を使用するよりも効率的です。insert()手がかりについては、ヒープソートの説明を参照してください。プログラムをテストするには、いくつかのアイテムを挿入し、さらに追加してから、ヒープを復元します。

最後にノードを正常に挿入し、ヒープ条件を変更しない toss 関数のコードを作成しました。ただし、機能に問題がありrestoreHeap、頭を包むことはできません。以下の2つの機能を含めました。

heap.java の完全なコードはこちら(toss()と を含むrestoreHeap())

toss()-これは挿入機能に基づいています

public boolean toss(int key)
{
    if(currentSize==maxSize)
        return false;
    Node newNode = new Node(key);
    heapArray[currentSize] = newNode;
    currentSize++;
    return true;
}  // end toss()

restoreHeap()- これは、trickleUp 関数に基づいており、StackOverflowError が発生しています。

public void restoreHeap(int index)
{
    int parent = (index-1) / 2;
    Node bottom = heapArray[index];

    while( index > 0 &&
            heapArray[parent].getKey() < bottom.getKey() )
    {
        heapArray[index] = heapArray[parent];  // move it down
        index = parent;
        parent = (parent-1) / 2;
    }  // end while
    heapArray[index] = bottom;
    while(index != 0)
    {
        restoreHeap(parent++);
    }

}  // end restoreHeap()

何か案は？助けていただければ幸いです。

4

1 に答える 1

1

やってみます。これは、いくつかの説明であなたが尋ねたことを行う方法です。

ヒープ内のすべてのノードの半分がリーフであり、リーフ自体が有効なヒープであることがわかっているため、ノードの残りの半分を実行して、それらも有効であることを確認するだけで済みます。これを下から上に行うと、ヒープを上に移動するときに有効なヒープ構造を「下」に維持できます。forこれは、ループによって簡単に実現できます。

 public void rebuildHeap()
 {
    int half = heapArray.length / 2;
    for(int i = half; i >= 0; i--)
        restoreHeap(i);
 }

それではどのようにrestoreHeap実装されますか？ノードをその子に対してチェックして、ノードindexを再配置する必要があるかどうかを確認することになっています。ノードの下のツリーindexがヒープであることを確認しているため、indexノードを正しい位置に移動するだけで済みます。したがって、ツリー内でそれを下に移動します。

まず、子供たちを見つける必要があります。3 つの行の各行には前の行の 2 倍のノードがあるため、子は次のように配置できます。

private void restoreHeap(int index)
{
    int leftChild = (index * 2) + 1;  //+1 because arrays start at 0
    int rightChild = leftChild +1;
    ...

index次に、子の値をノードの値と比較するだけです。index子の値が大きい場合は、ノードを子ノードと交換する必要があります。両方の子の値が大きい場合は、(スワップ後にヒープ構造を維持するために) 2 つのうち最大の値を持つ子と交換する必要があります。indexノードがスワップされたら、メソッドを再度呼び出して、ノードをツリーのさらに下に移動する必要があるかどうかを確認する必要があります。

    ...
    int biggest = index;
    if(leftChild < currentSize && heapArray[leftChild].getKey() > heapArray[index].getKey())
        biggest = leftChild;  //LeftChild is bigger
    if(rightChild < currentSize && heapArray[rightChild].getKey() > heapArray[biggest].getKey())
        biggest = rightChild; //RightChild is bigger than both leftChild and the index node

    if(biggest != index) //If a swap is needed
    {
        //Swap
        Node swapper = heapArray[biggest];
        heapArray[biggest] = heapArray[index];
        heapArray[index] = swapper;

        restoreHeap(biggest);
    }
}
于 2013-03-29T21:07:33.610 に答える