5

昨日質問したのですが、よく分からなかったので、具体的な質問です。

最小ヒープを配列として表しています。私はminheapsについてよく理解していると思いますが、その中の特定の概念については曖昧です。最小ヒープは、常にルートとして最小のノードを持つことになっています。値を削除するには、ルートを配列表現 (リーフ ノード) の最後の要素に設定し、配列のサイズを減らします。次に、siftDown/PercolateDown または任意の名前を使用して、ルート ノードを正しく配置します。これは超効率的です。例えば：

ツリー 1

ここでは、最後の要素から 29 が取得され、siftDown(1) によって配置されます。

  1. 29 を 15 および 38 と比較します。29 と 15 を交換します。
  2. 29 は 25 および 20 と比較されます。29 と 20 を交換します。
  3. 29 は 30 と比較され、29 < 30 であるため、これで完了です。

これで問題ありませんが、最小値を削除する 2 つのインスタンスの間に、他のデータの一部が変更された場合はどうなるでしょうか。例えば：

ツリー 2

ここでは、次のようにします。

  1. 29 を 15 および 38 と比較します。29 と 15 を交換します。
  2. 29 は 30 および 32 と比較されます。29 < 30 および 29 < 32 したがって、完了です。

1 はツリーの最小値ですが、最小値として設定されておらず、15 が設定されています。これは私にとって大きな問題です。Dijkstras アルゴリズムを実装しようとしています。Java 組み込みクラスに触れずに独自のデータ構造を使用しようとしています。

したがって、私の問題に関連するより適切な例は次のとおりです。

ここに画像の説明を入力

Dijkstras に精通している場合、99 は暫定的な無限距離を表し、その他の数字は次にアクセスする必要があるグラフ ノード (最小距離のノード、この場合は 3) を表します。

解決策は、min を削除するたびにツリーを再構築することですが、これは minheap の能力が失われ、実装が遅くなることを意味します。

これを正しく理解していない場合は申し訳ありませんが、何日もこれに悩まされており、本当に助けが必要です.

4

1 に答える 1

2

アルゴリズムの前提条件を理解する必要があります。このアルゴリズムsiftDownは、任意の配列では機能しません。左の子と右の子がヒープの場合にのみ機能します。

2 番目の例では、ルートの左の子は最小ヒープではありません。したがって、アルゴリズムは最小ヒープを生成しません。

画像番号 3 のように、ヒープ プロパティに違反する配列になった場合は、実装に何か問題があるはずです。

于 2016-04-19T13:50:28.887 に答える