問題タブ [fibonacci-heap]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
1 に答える
857 参照

java - O(1)償却時間で実行するためにフィボナッチヒープに減少キーを実装する方法は?

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

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

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

0 投票する
1 に答える
76 参照

data-structures - フィボナッチ ヒープがグローバル ノード カウンターを保持するのはなぜですか?

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

0 投票する
0 に答える
310 参照

c++ - フィボナッチヒープをブースト

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

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

0 投票する
2 に答える
1601 参照

c++ - ブースト フィボナッチ ヒープのパフォーマンスを向上させる方法

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

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

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

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

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

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

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

0 投票する
1 に答える
61 参照

algorithm - フィボナッチヒープ遅延はどのように可能な限り長く機能しますか?

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

0 投票する
1 に答える
2300 参照

algorithm - フィボナッチ ヒープのキーを減らす方法を理解するのに助けが必要

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

ここに画像の説明を入力

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