1

私は、文字列のヒープを作成し、それにさまざまな機能を実行するという課題に取り組んできました。現在、コードが正しく挿入されているかどうかをテストしていますが、そうではありません。私は単語をテストしています:Golf, Bravo, Hotel, Alpha, Delta, Echo, Charlie, Foxtrotアルファベット順に挿入されますが、ヒープを印刷すると次のようになります:

                                Alpha
             Bravo                              Charlie
   Foxtrot              Delta              Hotel              Echo
Golf

ここに私が書いたコードがあります：

public boolean insert(String key) {
    if(currentSize == maxSize) {
        return false;
    }

    Node newNode = new Node(key);
    heapArray[currentSize] = newNode;
    trickleUp(currentSize++);
    return true;
}

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

    while(index > 0 && heapArray[parent].getKey().compareTo(bottom.getKey()) > 0) {
        heapArray[index] = heapArray[parent];
        index = parent;
        parent = (parent - 1) / 2;
    }
    heapArray[index] = bottom;
}

編集:クイック検索を実行し、ヒープの別のソース コードを見つけてテストした後、同じ出力が得られました。これがアルファベット順に追加されていない理由はありますか?

4

1 に答える 1

0

印刷物に表示される動作は、最小ヒープに対して正しいです。次を参照してください。

http://en.wikipedia.org/wiki/Heap_(データ構造)

導入段落から（強調を追加）：

親ノードのキーが常に子ノードのキー以上であり、最上位のキーがルート ノードにある (この種のヒープは最大ヒープと呼ばれる) か、親ノードのキーがそれらのキー以下である子であり、最下位のキーはルート ノード (最小ヒープ) にあります。

2番目の段落から（強調を追加）：

兄弟またはいとこの間に暗黙の順序付けはなく、順序通りのトラバーサルの暗黙のシーケンスもありません (たとえば、二分探索ツリーにあるように)。上記のヒープ関係は、ノードとその直接の親の間でのみ適用されます。

ヒープは、各ノードがそれより大きい子のみをアルファベット順に持つという点で、正しく順序付けられているように見えます。

于 2013-07-29T00:20:12.033 に答える