確定一個節點是否存在於一個boost binomial_heap

Question

我想確定一個元素是否存在於boost :: heap :: binomial_heap因爲我需要知道我是否應該調用update（）（如果該節點已經存在）或push（）（如果節點不存在）。一些隊列恰恰爲此提供了一個push_or_update（）函數。我唯一能做的就是保留一個與隊列中的節點和value_type'handle_t'具有相同索引類型的屬性映射。然後，我可以在地圖上查找該項目是否有有效的句柄，以便我可以推送它，如果沒有，或者更新它。

有沒有更好的方法來做到這一點？

Here is the doc for reference。

Answer 1

這不是一個二項堆應該做的事情。

解決問題的常用方法是：使用哈希映射（或其他您喜歡的數據結構）來存儲值與handle之間的映射。然後可以查詢句柄的哈希映射。如果存在，該句柄將允許您修改堆中的值。如果它不存在，你可以在堆中添加一個新的值（當然，以及哈希映射中的一個新映射）

解決這個問題的另一種方法是使用樹集合/映射，它根據實際使用情況，比上述解決方案更容易，效率更高。