問題タブ [fibonacci-heap]

フィボナッチ ヒープのキーの減少操作で O(1) の償却複雑さを取得するにはどうすればよいですか? 要素を含むフィボナッチ ヒープ内のノードを見つけるだけでも、BFS を使用して O(n) 時間かかるため、O(1) 償却時間を取得することはできません。

参考までに、問題のノードを検索するための BFS の実装を次に示します。

そして、ここに私の減少キーのコードがあります:

フィボナッチ ヒープがグローバル ノード カウンターを保持していると読みましたが、その理由がわかりません。カウンターを持っていたが、まったく使用していない実装も見つけました。

ブースト フィボナッチ ヒープのコードを見ていましたが、多くの場所で、型 (テンプレートの一部) と呼ばれる変数が次のよう_idにID使用されているのを見ました。これの目的は何ですか。これと同等のものは、デフォルトの C++ 標準ライブラリのみです。get(_id, d)dT&T

フィボナッチ ヒープのコードは次のとおりです。

私はある種の連続的なダイクストラである Fast Marching アルゴリズムを実装しています。多くの論文で読んだように、フィボナッチ ヒープはこの目的に最も適したヒープです。

ただし、私のコードを callgrind でプロファイリングすると、次の関数が実行時間の 58% を占めていることがわかります。

具体的にpop()は、全体の実行時間の 57.67% を占めています。

heap_は次のように定義されます。

「そんなに」時間がかかるのは普通ですか、それともパフォーマンスを改善するためにできることはありますか?

十分な情報が提供されていない場合は申し訳ありません。できるだけ簡潔にしようとしました。必要に応じてさらに情報を追加します。

ありがとうございました！

私はCLRSを読んでいて、「フィボナッチヒープの遅延は可能な限り長く機能します」という行に出くわしました。

フィボナッチ ヒープ操作を実装する方法を理解しようとしています。次のヒープがあるとします。

たとえば、35 を 27 に減らすにはどうすればよいでしょうか。27 は 30 以下であるため、順序は保持されないため、ヒープを再構築する必要があります。では、27 はどこに行くのでしょうか。5歳未満？