0

バイナリ ヒープの最小数を削除しようとしていますが、最小値を削除できるのは 1 回だけですが、もう一度削除しようとすると、0 が返されません。最小値がなくなったヒープだけが返されます。問題をデバッグしようとしましたが、何の利益も得られませんでした。私が見ていないものを見ることができる人がいたら、問題を理解するのを手伝ってくれませんか? 前もって感謝します。例、1-6 からヒープに挿入した後、ヒープに 5 6 1 2 3 4 があり、最小を削除すると 2 3 4 5 6 が出力されます。しかし、その後 Min を削除すると、代わりに 0 が出力されます3 4 5 6. この問題を解決するための助けをいただければ幸いです。

public class BHeap {

public int RemoveMin(){

            while( curr != null ) {
        if( curr.key < found.key ){
            found = curr;
            p_o = prev;
        }
        prev = curr;
        curr = curr.rightSibling;
    }

    this.root = merge(found.leftmostChild);
    return result;
}
4

1 に答える 1

2

ヒープ (ここでは最小ヒープ) を実装するときは、一般的に 3 つの方法に分割する必要があると思います。

-Heapify (ヒープの要素に対して呼び出されます: 1. {element, element.right, element.left} から最小の要素を選択します。2. 必要に応じて (要素が 3 つの中で最小でない場合)、最小の要素を交換します。要素を 3 つ使用し、要素を再帰的に処理してヒープを完全に固定します)、

-BuildHeap (適切に Heapify を呼び出すだけ),

-Extract-Min (1. 最上位の要素をヒープの一番右 (最下位レベルの最後) の要素と交換します。2. 既に交換された最小の要素を削除します。3. 新しい最上位の要素 (交換したばかり) で heapify を呼び出します。ヒープを修復します。

また、ヒープは主にテーブル構造として使用される構造であり、ノード構造ではないと考えています。Cormen、Leiserson、Rivest、Stein による「Introduction to Algorithms」は、優れた理論的基盤を提供します。

あなたの実装に関しては、私が理解している限り、見つかったものを現在のルート (ヒープ内の最小の要素) に設定してから、ヒープ内のより小さな要素を検索します。ルートよりも小さいキーを持つ要素が見つからないか、最小ヒープではありません!

于 2013-11-01T23:02:37.297 に答える