0

だから私はバイナリ最小ヒープを実装しようとしています。バイナリ最小ヒープがその構造とプロパティに関して何を伴うかを理解しています。ただし、ポインターとノードを使用して実装しようとすると、壁にぶつかります。

、およびを使用してNodeいます。挿入された最後のノードを指す場所もあります。right/left and pointersint elementparent pointerLastNode

私の口論は、最後のノードに関して、要素を挿入するときに何をすべきかわからないということです。これが私の言いたいことです。

ステップ 1.) ヒープが空であると仮定します。rootつまり、x に要素が含まれる x を作成し、 および を設定root.left/right = nullしLastNode = root.leftます。

  X
 / \
0   0

これは私が立ち往生している部分です。別の要素を格納するために別のノードを作成すると、それは X の左側または LastNode が指す場所になることを私は知っています。私の質問 LastNode で次に何をすればよいですか? x.right を指すようにしますか? 私はinsert(int x)logN で実行し続けようとしています。lastNode の操作は、各レベルでより長く、より広範囲になります。

誰かがそれを分解できますか？ありがとう

4

5 に答える 5

1

最下位レベル、つまり幅方向にノードを挿入する必要があるため、これまでに挿入されたすべてのノードの記録をキューに保持するとどうなるでしょうか? ヒープに新しいノードを挿入するときは、キューから最新の位置を見つけて、そこにデータを挿入します。次に、そのノードを heapify_up します。

于 2012-04-04T03:16:21.163 に答える
1

ヒープの最後のレベルに要素を挿入し、そこからバブルアップする必要があるかどうかを判断する必要があります。したがって、最後に挿入された要素ではないことを示すために lastNode ポインターが必要です (最後に挿入された要素である可能性は非常に高いですが、現在はルートになっている可能性があります。これはまったく役に立ちません)。この新しい要素を挿入する場所。それは役に立ちますか？

（後で編集）：ヒープを構築するためのより最適な方法がありますが、それはあなたが今必要としているものではないと感じているので、すべての新しいエレメント。

于 2011-04-01T22:16:30.310 に答える
0

私も同じ宿題でした。私が見つけた解決策は、二分木をレベルごとに下げ​​、そのたびに下部のノードの数に応じて左折または右折を決定することです。このための再帰アルゴリズムを作成しました。

たとえば、次のツリーに新しいノードを配置するとします。

    A
   / \
  B   C
 / \ / \
D  E X  X

上部から始めて、下部に 2/4 のフル ノードがあることがわかります。したがって、右の枝を通って降りると、 root のあるツリーの一番上にいることに気づきCます。このツリーの最下部には 0/2 の完全なノードがあるため、左側の分岐を経由して下降し、リーフ ノードにいることに気付くので、そこに新しい要素を配置します。

これは、ツリーの高さ、特定の高さのツリーの下部にある可能なノードの数、およびサイズのツリーの下部にある完全なまたは「使用された」ノードの数を計算するために使用した Java コードですsize。

private int height(int size) {
    return (int) Math.ceil(log2(size + 1));
}
// returns the amount of space in the bottom row of a binary tree
private int bottomRowSpace(int height) {
    return (int) Math.pow(2, height - 1);
}
// returns the amount of filled spots in the bottom row of a binary tree
private int bottomRowFilled(int size) {
    return size - (bottomRowSpace(height(size)) - 1);
}
// log base2
private double log2(double a) {
    return Math.log(a) / Math.log(2);
}
于 2015-06-23T05:58:07.680 に答える