0

要素が boost::heap::binomial_heap に存在するかどうかを判断しようとしています。これは、 update() (ノードが既に存在する場合) または push() (ノードが存在しない場合) を呼び出す必要があるかどうかを知る必要があるためです。一部のキューは、まさにこの目的のために push_or_update() 関数を提供します。私が理解できる唯一のことは、キュー内のノードと同じインデックス タイプと value_type 'handle_t' を持つプロパティ マップを維持することです。次に、アイテムに有効なハンドルがあるかどうかをマップで検索して、そうでない場合はプッシュし、有効な場合は更新できます。

これを行うより良い方法はありますか？

参照用のドキュメントは次のとおりです。

4

1 に答える 1

0

これは、二項ヒープが行うべきことではありません。

handle問題を解決する通常の方法は次のとおりです。値とs の間のマッピングを格納するために、ハッシュ マップ (または他の好きなデータ構造) を使用します。次に、ハンドルのハッシュ マップをクエリできます。存在する場合、このハンドルを使用してヒープ内の値を変更できます。存在しない場合は、ヒープに新しい値を追加するだけです (もちろん、ハッシュ マップ内の新しいマッピングも)。

この問題を解決する別の方法は、ツリー セット/マップを使用することです。これは、実際のユース ケースによっては、上記の解決策よりも簡単で効率的な場合があります。

于 2012-09-05T23:38:23.600 に答える