0

Weiss の「Data Structures and Algorithms In Java」では、バイナリ ヒープの挿入アルゴリズムについて次のように説明しています。

public void insert( AnyType x )
{
    if( currentSize == array.length -1)
        enlargeArray( array.length * 2 + 1);

    // Percolate up
int hole = ++currentSize;
for(array[0] = x; x.compareTo( array[ hole / 2 ]) < 0; hole /=2 )
    array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;
}

穴をツリーの上に移動するという原則は理解できますが、for ループでこの構文を使用して彼がそれをどのように達成しているのか理解できません... 初期化子のarray[0] = x;意味は何ですか? 彼はルート値を上書きしているようですか？非常に不自然なコードのようです。彼は何をしているのですか？

4

2 に答える 2

1

まず、Mark Weiss から返信があり、彼のメールには基本的にコードが正しいと書かれていました (この回答の最後に完全な返信があります)。

彼はまたこう言った：

したがって、findMin に示すように、最小項目は配列インデックス 1 にあります。挿入を行うには、下からルートまでのパスをたどります。

インデックス 1? うーん...その後、戻って章の大部分を読み直す必要があり、図 6.3 を見てクリックしました。

配列は 0 ベースですが、ヒープの一部と見なされる要素はインデックス 1 以降に格納されます。図 6.3 は次のようになります。

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   | A | B | C | D | E | F | G | H | I | J |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9  10  11  12  13

要素 0 に値を配置することは、ループを終了させるためのセンチネル値です。

したがって、上記のツリーを使用して、挿入機能がどのように機能するかを見てみましょう。H下が穴のマーク。

まずx、0 番目の要素 (ヒープの外側) に配置し、配列内の次の使用可能な要素に穴を配置します。

                                              H
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| x | A | B | C | D | E | F | G | H | I | J |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9  10  11  12  13

次に、穴をバブルアップ (パーコレート) し、x.

図 6.5 と 6.6 を見て、実際の値を配列に入れましょう。

                           H/2                           H
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 |    |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13

挿入する値である 14 をインデックス 0 に配置したことに注意してください。ただし、これはヒープの外側にあり、ループを確実に終了させるためのセンチネル値です。

次に、値xを の値と比較しますhole / 2。現在は 11/2 = 5 です。x は 31 より小さいので、値を上に移動し、穴を移動します。

            H/2             H <---------------------------
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 | 31 |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13
                            |                             ^
                            +--------- move 31 -----------+

もう一度比較すると、14 は 21 よりも小さい (5 / 2 = 2) ため、もう一度:

       H/2   H <------------
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13
             |              ^
             +-- move 21 ---+

ただし、14 は 13 より小さくない (穴 / 2 --> 2 / 1 = 1) ため、次の正しい場所を見つけましたx。

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 14 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 |    |    |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11   12   13
             ^
             x

図 6.6 と 6.7 を見るとわかるように、これは予想される動作と一致します。

したがって、コードは間違っていませんが、おそらく本の範囲外である小さな障害が 1 つあります。

挿入されるタイプがx参照タイプの場合、現在のヒープには、挿入された同じオブジェクトへの 2 つの参照があります。次に、ヒープからオブジェクトをすぐに削除すると、0 番目の要素がまだ参照を保持しているように見えます (ただし、最初の場所にあるように見えます...)。

ここに隠された議題がないことを確認するために、マークからの完全な回答を次に示します。

ラッセさん、こんにちは。

コードは正しいです。

バイナリ ヒープは完全なバイナリ ツリーであり、底からルートまでのどのパスでも、値が増加することはありません。したがって、最小項目はルートにあります。配列表現はルートをインデックス 1 に配置し、インデックス i の任意のノードについて、親は i/2 (切り捨て) にあります (左の子は 2i にあり、右の子は 2i+1 にありますが、これは必要ありません)ここ）。

したがって、findMin に示すように、最小項目は配列インデックス 1 にあります。挿入を行うには、下からルートまでのパスをたどります。

for ループでは:

hole /= 2 は、穴を親に移動するという考えを表しています。

x.compareTo( array[ hole / 2 ]) < 0 は、x が親よりも小さい限り、ループにとどまるという考えを表しています。

問題は、x が新しい最小値である場合、安全にループから抜け出せないことです (技術的には、x と配列 [0] を比較しようとするとクラッシュします)。コーナーケースを処理するために追加のテストを入れることができます。または、コードは最初に x を array[0] に配置することで回避します。ノード i の「親」は i/2 であるため、インデックス 1 にあるルートの「親」はインデックスで見つけることができます。 0. これにより、x が新しい最小値である場合にループが終了することが保証されます (そして、インデックス 1 のルートに新しい最小値である x が配置されます)。

より長い説明は本にあります... しかし、ここでの基本的な概念は、センチネル (またはダミー) 値を使用して、境界ケースの余分なコードを回避することです。

よろしく、

マーク・ワイス

于 2014-11-06T08:04:15.083 に答える