問題タブ [fibonacci-heap]

C++ プライオリティ キューはダイクストラ キューに適した構造ではないと思います。要素を簡単に検索または削除するための機能が含まれていないからです。

正しい構造はフィボナッチ ヒープですが、std ライブラリにはありません。

より優れた C++ 実装の構造について提案がある人はいますか?

要素が削除された後、消去操作はヒープも更新しますか?

fibonacci_heap のブースト ドキュメントでメンバー関数の説明を確認しました。ここでは、増加/減少操作の後に何が起こるかについて言及されていますが、消去に関しては、ハンドルが指す要素を消去するということだけが述べられています。

その後、ヒープが再形成されるということですか？そうでない場合、消去されたノードの子ノードはどうなりますか? 明らかな何かが欠けていますか？

グラフの隣接リスト表現を持つフィボナッチヒープを使用して、ノード間の最短パスを見つけるためのダイクストラのアルゴリズムを実装しようとしています。私が知っているアルゴリズムによると、ヒープ内の最小ノードを見つけてから、そのすべての隣接ノードを繰り返し処理し、それらの距離を更新する必要があります。しかし、隣人の現在の距離 (ヒープ内の各ノードに格納されている) を取得するには、ヒープからその特定のノードを見つける必要があります。「検索」操作には O(N) 時間かかります。ここで、N はフィボナッチ ヒープ内のノード数です。私のアルゴリズムは正しいですか、それとも何か不足していますか? どんな助けでも大歓迎です。

実装でブーストからフィボナッチヒープを使用しようとしていますが、減少関数を呼び出すとプログラムがクラッシュします。これは例です(Wは単純なクラスです):

boost::fibonacci_heap ライブラリを使用して Fast Marching アルゴリズムを実装しており、ハンドルを使用して要素を操作し始めていました。

以下の基本的なコードを書きました。コンパイルはうまくいきますが、動作がわかりません。

最初に、プッシュされた各要素のハンドルを配列に格納します。次に、ヒープから最初の要素を取り出し、ヒープ サイズが減少したことを確認します。

しかし、そのハンドルを使用して、ポップアウトされた要素の値を更新しようとします。この操作は (驚くべきことに?) 機能し、更新された要素はヒープの一番上にあります。ただし、新しい要素を適切にプッシュしていないため、ヒープ サイズは同じままです。

では、ポップアウトされた要素が更新されてヒープに戻るとどうなるでしょうか? ヒープはまだ有効ですか?

端末出力:

フィボナッチ ヒープは減価償却という意味では効率的ですが、最悪の場合はどれくらい効率的でしょうか? 具体的には、n ノードのフィボナッチ ヒープに対するこれらの各操作の最悪の場合の時間計算量はどれくらいですか?

• 分を見つける
• 削除分
• 入れる
• キーを減らす
• マージ