だから、ここで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)
ここで、H1 と H2 はヒープまたはノードであると仮定しますか? ここで、Java で何をすべきかについて少し混乱します。
次に、次の部分については、そうする必要があるように見えますk.left = H1。k.right = H2
「k at root」と表示されるタイミングがよくわかりません。kルート ノードではありませんか。その場合、ダウンヒープ バブルkも同様に実行しますか? では、最後はこの時点でもH？k
投稿するコードがないのは残念ですが、エラーは再帰呼び出しのサブリストにあります。
更新しました：
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;
}
ありがとう！