1

だから、ここでbottomupheapアルゴリズムを実装しようとしています: http://www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html

アルゴリズムbottomUpHeap(S)
入力: 2h-1 キーを格納するシーケンス S
出力: S にキーを格納するヒープ H
S が空の場合
    空のヒープを返す
S から最初のキー k を削除する
S をそれぞれ (n-1)/2 のサイズのサブシーケンス S1 と S2 に分割します。
H1¬ ボトムアップヒープ(S1)
H2¬ ボトムアップヒープ(S2)
k がルート、H1 が左側のサブツリー、H2 が右側のサブツリーであるようなバイナリ ツリー H を作成します。
必要に応じてルートからダウンヒープ バブリングを実行する
Hを返す

Javaでプログラミングしてからしばらく経ちましたが、不明なエラーが発生し続けています。アルゴリズムのステップのいくつかを片付けて、誰かが私を助けてくれるかどうか疑問に思っていました.

データと左右の参照ポインター (または Java がそれらを呼び出すもの) を使用してヒープ ノードを作成しました。入力シーケンスは、に変換される配列ですArrayList。それが上記の関数に渡すものです。

S から最初のキーを削除し、そのキーで新しいノードを作成します。私の例では、Integers を使用しているだけで、キーはデータ参照に設定されています。

私はそれから使用 S1 = S.sublist(0, S.length/2) し、 S2 = S.sublist(S.length/2, S.length)

私がこれまでに持っているものは次のとおりです。

AnArrayListは S として渡されます。Treeは として定義されTree(data, left, right)ます。ありがとう。

private Tree Heapify(List<Integer> S){

    if (S.isEmpty()){
        Tree emptyHeap = new Tree();
        return emptyHeap;
    }

    int tmpk = S.get(0);
    S.remove(0);

    int halfArr = S.size()/2;

    List<Integer> S1 = S.subList(0, halfArr);
    List<Integer> S2 = S.subList(halfArr, S.size());

    Tree k = new Tree(tmpk, Heapify(S1), Heapify(S2));

    //Downheap.
    return null;
}

空のリストが渡されると、何らかの理由でサブリストを使用するときに空のリストとは見なされないようです。S.isEmpty() などの空で何かをしようとすると、エラーがスローされるようです。

ありがとう！

4

2 に答える 2

0

私はこれを以前に経験しましたが、結論はあなたが使用しなければならないということです:

S1 = new ArrayList(S.sublist(0, S.length/2));

javadocからは少しわかりにくいsublistですが、指定された範囲の元のリストのビューのみを返します。ソースコードを見て、魔法が起こっていることを確認してください。

それでもこれを保持したい場合は、私の意見では完全にぎこちなく、s.size() == 0の代わりに抽象化を使用することをお勧めしますs.isEmpty()。ああ、慣例では、変数はキャメルケースで宣言されています。

于 2011-02-15T20:39:13.347 に答える
0

removeリストを繰り返し処理している間はできません。

これを行う：

プライベート ツリー heapify(リスト リスト){

        if (list.isEmpty()){
            null を返します。
        }

        int tmpk = list.get(0);
// list.remove(0);
        リスト s1 = null;
        リスト s2 = null;
        list = list.subList(1, list.size()); // 代わりにリストを変更します

        int halfArr = list.size()/2;

        s1 = list.subList(0, halfArr);
        s2 = list.subList(halfArr, list.size());

        ツリー k = new Tree(tmpk, heapify(s1), heapify(s2));

        k を返します。
    }
于 2011-02-15T21:00:08.813 に答える