data-structures - フィボナッチヒープのいくつかのノードをマークする目的は何ですか？

Question

ウィキペディアの記事からのこの写真には、青でマークされたフィボナッチヒープの3つのノードがあります。このデータ構造でマークされているノードのいくつかの目的は何ですか？

Answer 1

直感的には、フィボナッチヒープはさまざまな順序のツリーのコレクションを維持し、delete-minが発生するとそれらを合体させます。フィボナッチヒープを構築する際の希望は、各ツリーが多数のノードを保持することです。各ツリーのノードが多いほど、ツリーに格納する必要のあるツリーの数が少なくなるため、各削除分でツリーを合体させるために費やされる時間が少なくなります。

同時に、フィボナッチヒープは、キー減少操作を可能な限り高速化しようとします。これを行うために、フィボナッチヒープを使用すると、サブツリーを他のツリーから「切り取り」、ルートに戻すことができます。これにより、decrease-keyは高速になりますが、各ツリーが保持するノードが少なくなります（また、ツリーの数も増えます）。したがって、設計の構造には基本的な緊張があります。

これを機能させるには、フィボナッチヒープのツリーの形状をいくらか制限する必要があります。直感的には、フィボナッチヒープ内のツリーは、少数の子を失うことが許可されている二項ツリーです。具体的には、フィボナッチヒープ内の各ツリーは、後のステップでそのツリーを「再処理」する必要がある前に、最大2つの子を失うことが許可されます。フィボナッチヒープのマーキングステップにより、データ構造はこれまでに失われた子の数をカウントできます。マークされていないノードは子を失いませんでした。マークされたノードは1つの子を失いました。マークされたノードが別の子を失うと、2つの子が失われるため、再処理のためにルートリストに戻す必要があります。

これが機能する理由の詳細は、多くの入門アルゴリズムの教科書に記載されています。これがまったく機能するかどうかは明らかではなく、計算には少し注意が必要です。

うまくいけば、これは有用な直感を提供します！

Answer 2

子ノードの1つが減少キーのために切断されると、ノードがマークされます。2番目の子が切り取られると、ノードもその親から切り取られます。マーキングは、2番目のカットがいつ発生するかがわかるように行われます。

Answer 3

Wikiからの適切な説明：操作減少キーはノードを取得し、キーを減少させ、ヒーププロパティに違反した場合（新しいキーが親のキーよりも小さい場合）、ノードはその親から切断されます。親がルートでない場合は、マークが付けられます。すでにマークされている場合は、それもカットされ、その親がマークされます。ルートまたはマークされていないノードに到達するまで、上向きに進みます。ここで、最小ポインタが新しい最小値である場合は、減少した値に設定します。