要素が削除された後、消去操作はヒープも更新しますか?
fibonacci_heap のブースト ドキュメントでメンバー関数の説明を確認しました。ここでは、増加/減少操作の後に何が起こるかについて言及されていますが、消去に関しては、ハンドルが指す要素を消去するということだけが述べられています。
その後、ヒープが再形成されるということですか？そうでない場合、消去されたノードの子ノードはどうなりますか? 明らかな何かが欠けていますか？
1 に答える
4
フィボナッチ ヒープから要素を消去すると、ツリーが再統合されます。原則として、フィボナッチ ヒープに対する操作の償却時間が O(log(N)) の場合、ツリーの統合が発生しています。
概念的には、削除操作は次の 2 つの操作の組み合わせと考えることができます。
- min-heap 実装の場合、Delete は Decrease-Key (O(1)) と Extract-Min (O(log(n))) の組み合わせです。
- 最大ヒープ実装の場合、Delete は Increase-Key (O(1)) と Extract-Max (O(log(n))) の組み合わせです。
実際には、不要なステップを避けるために実装が最適化されることがよくありますが、償却された対数の複雑さは同じままです。Boost.Heap のfibonacci_heap::erase()実装の場合:
于 2015-03-10T16:28:39.207 に答える