問題タブ [fibonacci-heap]

フィボナッチ ヒープを理解するのは難しいことがわかっています。しかし、いくつかの質問は私には本当に不明確です:

• t + 2m のような潜在的な関数を選択するのはなぜですか? 理由は何ですか？
• ノードのマーキングの背後にある理由は何ですか?ノードをルート リストなどに配置すると便利だと思いますが、なぜそのようなスキームを考え出すのでしょうか?

ありがとう！

フィボナッチヒープに二項ツリーではないツリーを含めることは可能ですか? もしそうなら、これはどのように起こりますか？例を挙げていただけますか？

Q. 要素をフィボナッチ ツリーにどのように挿入しますか。フィボナッチ木は選別された木に似ているので、私は考えていました。右の木か左の木の​​バランスをとる必要があります。しかし、どのように？

私は初心者レベルのコンピュータープログラミングクラスに参加しており、（他の3人の学生と一緒に）最終プロジェクトにフィボナッチヒープを実装したいと考えています。誰かがフィボナッチヒープのいくつかの良いアプリケーションを提案できますか？良いプレゼンテーション資料になるほど派手なものはありますか？

新しい「ヒープ」ブーストライブラリには、フィボナッチヒープが含まれています。各実装の複雑さは、 http：//www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structures.htmlで確認できます。

私の質問はこれです：増加操作がO（1）であるのに、なぜフィボナッチヒープ減少操作O（log（N））なのですか？

ダイクストラのアルゴリズムでフィボナッチヒープを使用して実験したいと思います。これは、高速減少操作に大きく依存しています。

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

STLのフィボナッチヒープはどこにありますか？STLがフィボナッチヒープを実装していない場合、STLの既存のアルゴリズムとコンテナを使用してフィボナッチヒープを実装するためのベストプラクティスは何ですか？

私はフィボナッチヒープについて学ぼうとしていました。ヒープに要素を挿入するための擬似コードは次のとおりです。

これが私が理解していなかったいくつかのことです、

• root list containing xHを含むルートリストとそれを連結する方法とは何ですか？

minを抽出している間、次のようなことを行います。

（ここに他の機能があります、統合してリンクします、http：//www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html）

• 前の挿入関数では、子を設定し、xのpをnilとして設定し、minを抽出している間、if <> nil常にfalseになるため、関数を数回呼び出すと、正確なminが得られません。

• この構造がフィボナッチ「ヒープ」と呼ばれる場合、ヒーププロパティはどこで維持されますか？

• フィボナッチヒープの代わりにダイクストラのアルゴリズムでバイナリヒープを使用する場合、配列またはリンクリストを使用する場合とほぼ同じくらい時間がかかりますか？

誰かが私が抱えている困難を説明できますか？ありがとうございました。

n 個のノードを持つフィボナッチ ヒープの高さが n になることを示したいと思います。

例でこれを試しましたが、これを一般的に示す方法がわかりません。

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

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

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