19

フィボナッチ ヒープデータ構造の名前には「フィボナッチ」という単語が含まれていますが、データ構造にはフィボナッチ数が使用されているようには見えません。ウィキペディアの記事によると：

フィボナッチヒープの名前は、実行時間分析で使用されるフィボナッチ数に由来します。

これらのフィボナッチ数は、フィボナッチ ヒープでどのように発生しますか?

4

2 に答える 2

23

フィボナッチ ヒープは、特定の構造上の制約に従うさまざまな「順序」のヒープ順序ツリーの集合で構成されています。フィボナッチ数列が発生するのは、次数 n のツリーに少なくとも F n+2個のノードが含まれるようにこれらのツリーが構築されるためです。ここで、F n+2は (n + 2) 番目のフィボナッチ数です。

この結果が正しい理由を確認するために、フィボナッチ ヒープのツリーがどのように構築されるかを確認することから始めましょう。最初に、ノードがフィボナッチ ヒープに配置されるたびに、そのノードだけを含む次数 0 のツリーに配置されます。値がフィボナッチ ヒープから削除されるたびに、フィボナッチ ヒープ内のいくつかのツリーが合体され、ツリーの数が大きくなりすぎないようにします。

ツリーを結合する場合、フィボナッチ ヒープは同じ順序のツリーのみを結合します。次数 n の 2 つのツリーを結合して次数 n + 1 のツリーにするために、フィボナッチ ヒープは 2 つのツリーのうちルート値が大きい方を取得し、そのツリーをもう一方のツリーの子にします。この事実の 1 つの結果は、次数 n の木には常に正確に n 個の子があるということです。

フィボナッチ ヒープの主な魅力は、(償却された O(1) で) 減少キーを効率的にサポートすることです。これをサポートするために、フィボナッチ ヒープは次のように減少キーを実装します。あるノードに格納されている値のキーを減少させるために、そのノードは親ツリーから切り取られ、独自の別のツリーとして扱われます。これが発生すると、古い親ノードの順序が 1 つ減ります。たとえば、次数 4 のツリーから切り取られた子がある場合、次数 3 のツリーに収縮します。これは、ツリーの次数が含まれる子の数であると想定されているためです。

これを行う際の問題は、あまりにも多くのツリーが同じツリーから切り落とされると、ツリーの順序が大きくなり、ノードの数が非常に少なくなる可能性があることです。フィボナッチ ヒープの時間保証は、大きな順序を持つツリーに膨大な数のノードが含まれている場合にのみ可能です。必要なノードをツリーから切り取ることができれば、巨大な順序を持つツリーが簡単に作成される状況に陥る可能性があります。少数のノードのみが含まれます。

これに対処するために、フィボナッチ ヒープには 1 つの要件があります。ツリーから 2 つの子を切り取る場合は、そのツリーを親から切り取る必要があります。 これは、フィボナッチ ヒープを形成するツリーがキーの減少によってそれほどひどく損傷されないことを意味します。

そして今、フィボナッチ数に関する部分に取り掛かることができます. この時点で、フィボナッチ ヒープのツリーについて次のことが言えます。

  • 次数 n の木には、正確に n 個の子があります。
  • 次数 n のツリーは、次数 n - 1 の 2 つのツリーを取り、一方を他方の子にすることによって形成されます。
  • ツリーが 2 つの子を失うと、そのツリーは親から切り離されます。

では、これらの仮定の下で作成できる最小のツリーはどれかを尋ねることができます。

いくつかの例を試してみましょう。次数 0 の可能なツリーは 1 つだけで、これは単一のノードです。

Smallest possible order 0 tree:      *

次数 1 の可能な最小のツリーは、少なくとも子を持つノードである必要があります。作成できる最小の子は、次のツリーである最小の順序 0 ツリーを子として持つ単一のノードです。

Smallest possible order 1 tree:      *
                                     |
                                     *

次数 2 の最小の木はどうなるでしょうか。ここからが興味深いところです。この木は確かに 2 つの子を持つ必要があり、次数 1 の 2 つの木をマージすることによって形成されます。したがって、木には最初に 2 つの子 (次数 0 の木と次数 1 の木) があります。それらをマージした後、木から子供を切り取ってください！この場合、次数 1 の木の子を切り取ると、次数 0 の木である 2 つの子を持つ木が残ります。

Smallest possible order 2 tree:      *
                                    / \
                                   *   *

注文3はどうですか？以前と同様に、このツリーは次数 2 の 2 つのツリーをマージすることによって作成されます。次に、この次数 3 のツリーのサブツリーをできるだけ多く切り取ろうとします。作成されると、ツリーには次数 2、1、および 0 のサブツリーがあります。次数 0 のツリーから切り離すことはできませんが、次数 2 および次数 1 のツリーから 1 つの子を切り取ることはできます。これを行うと、次数 1 の 1 つと次数 2 の 2 つの 3 つの子を持つツリーが残ります。

 Smallest possible order 3 tree:       *
                                      /|\
                                     * * *
                                     |
                                     *

これで、パターンを見つけることができます。可能な最小の次数 (n + 2) ツリーは、次のように形成されます。次数 n + 1、n、n - 1、...、2 の子を持つ通常の次数 (n + 2) ツリーを作成することから始めます。 , 1, 0. 次に、同じノードから 2 つの子を切り取らずに、ノードを切り離してツリーをできるだけ小さくします。これにより、次数 n、n - 2、...、1、0、および 0 の子を持つツリーが残ります。

これらのツリーにいくつのノードがあるかを判断するために、再帰関係を記述できるようになりました。これを行うと、次のようになります。ここで、NC(n) は、次数 n のツリーに含まれるノードの最小数を表します。

NC(0) = 1
NC(1) = 2
NC(n + 2) = NC(n) + NC(n - 1) + ... + NC(1) + NC(0) + NC(0) + 1

ここで、最後の +1 はルート ノード自体を示しています。

これらの用語を展開すると、次のようになります。

NC(0) = 1
NC(1) = 2
NC(2) = NC(0) + NC(0) + 1 = 3
NC(3) = NC(1) + NC(0) + NC(0) + 1 = 5
NC(4) = NC(2) + NC(1) + NC(0) + NC(0) + 1 = 8

お気付きかもしれませんが、これはまさにフィボナッチ数列を 2 桁ずらしたものです。つまり、これらの各ツリーには、少なくとも F n+2個のノードが必要です。ここで、F n + 2は (n + 2) 番目のフィボナッチ数です。

では、なぜフィボナッチ ヒープと呼ばれるのでしょうか。 次数 n の各ツリーには、少なくとも F n+2個のノードが含まれている必要があるためです。

興味がある方は、フィボナッチ ヒープに関する元の論文に、これらの可能な限り小さい木の写真が掲載されています。見るのはかなり気の利いたです！また、フィボナッチ ヒープ ツリーのサイズが異なる理由については、この CS Theory Stack Exchange Postを参照してください。

お役に立てれば！

于 2013-01-15T07:56:21.983 に答える
5

私自身が「あはは！」を持っていたことを直感的に説明したいと思います。との瞬間。

ツリー構造は、高さに関して指数関数的な数のアイテムを格納できるため、O(log n) ランタイムを実現します。二分木は 2^h を格納でき、三分木は 3^h を格納でき、一般的なケースとして x^h についても同様です。

x が 2 未満になることはありますか? 確かにそれはできます！x > 1 である限り、ログ ランタイムと、その高さに対して指数関数的に多くのアイテムを格納する機能を実現できます。しかし、どうやってそのような木を作るのでしょうか? フィボナッチ ヒープは、x ≈ 1.62、または黄金比のデータ構造です。黄金比に出会うたびに、どこかにフィボナッチ数が潜んでいます...

フィボナッチ ヒープは実際には木の森です。「統合」と呼ばれるプロセスの後、これらの各ツリーには、正確に 2 のべき乗であるアイテムの個別の数が保持されます。たとえば、フィボナッチ ヒープに 15 のアイテムがある場合、1、2、4、および 8 を保持する 4 つのツリーがあります。アイテムはそれぞれ次のようになります。

ここに画像の説明を入力

「統合」プロセスの詳細は関係ありませんが、本質的には、すべての木が異なる次数になるまで、基本的にフォレスト内の同じ次数のツリーを結合し続けます (これらの木がどのように構築されるかをクールな視覚化で確認してください)。任意の n を正確に 2 のべき乗の合計として記述できるため、フィボナッチ ヒープの統合されたツリーが任意の n に対してどのように見えるかを想像するのは簡単です。

OK、これまでのところ、フィボナッチ数との直接的な関係はまだ見られません。彼らはどこで写真に登場しますか？それらは実際には非常に特殊なケースで表示されます。これは、フィボナッチ ヒープが DECREASE-KEY 操作に O(1) 時間を提供できる理由の鍵でもあります。キーを減らすとき、新しいキーがまだ親のキーよりも大きい場合は、min-heap プロパティに違反していないため、他に何もする必要はありません。しかし、そうでない場合は、小さな子を大きな親の下に埋もれたままにすることはできないため、そのサブツリーを切り取り、そこから新しいツリーを作成する必要があります。明らかに、削除ごとにこれを実行し続けることはできません。そうしないと、ツリーが高すぎて指数関数的な項目がなくなり、抽出操作に O(log n) 時間がかからなくなるためです。問題は、ツリーにその高さの指数項目が残るように、どのようなルールを設定できるかということです。巧妙な洞察は次のとおりです。

We will allow each parent to loose up to one child. If there is a subsequent attempt to remove another child from same parent then we will cut that parent also out of that tree and put it in root list as tree of 1.

上記のルールにより、最悪の場合でも、木にはその高さの指数項目が残ることが保証されます。最悪のケースは何ですか？最悪のケースは、各親に 1 人の子供を失う場合に発生します。親が 1 つ以上の子を持っている場合、どちらを取り除くかを選択できます。その場合、最大のサブツリーを持つ子を取り除きましょう。上の図で、親ごとにこれを行うと、サイズ 1、1、2、および 3 のツリーが作成されます。ここにパターンがありますか? 楽しみのために、次数 4 (つまり 16 アイテム) の新しいツリーを上の図に追加して、各親に対してこのルールを実行した後に何が残るかを推測してください: 5. ここにフィボナッチ数列があります!

フィボナッチ数列は指数関数的であるため、各ツリーは依然として指数関数的な数のアイテムを保持するため、EXTRACT-MIN 操作の実行時間は O(log n) になります。ただし、DECREASE-KEY は O(1) しかとらないことに注意してください。もう 1 つのすばらしい点は、任意の数をフィボナッチ数の和として表現できることです。たとえば、32 = 21 + 8 + 3 は、フィボナッチ ヒープに 32 個のアイテムを保持する必要がある場合、それぞれ 21、8、3 個のアイテムを保持する 3 つのツリーを使用してそれを行うことができることを意味します。ただし、「統合」プロセスでは、フィボナッチ数のノードを持つツリーは生成されません。これらは、DECREASE-KEY または DELETE の最悪のケースが発生した場合にのみ発生します。

参考文献

  • 二項ヒープ- フィボナッチ ヒープは、基本的に遅延二項ヒープです。バイナリ ヒープ以外の高さの指数項目をツリーに格納する別の方法を示しているため、これは優れたデータ構造です。
  • フィボナッチ ヒープの背後にある直感フィボナッチ ヒープをその核心で理解したい人は必読です。多くの場合、教科書はこの主題について浅すぎて雑然としすぎていますが、この SO 回答の著者はそれを明確にしています。
于 2014-12-27T09:13:20.617 に答える