STL重新實現

Question

在圖算法中，我需要找到最小值的節點。

在該算法的一個步驟中，可以減少該節點或其鄰居的值，並且可以根據它們的值來移除它的一些節點。 此外，我不想每次搜索此節點的整個圖（雖然它不是很大（< 1000個節點））。

因此，我看着STL庫，發現堆結構幾乎做我想要的。我可以非常快地插入和刪除節點，但是有沒有一種方法可以在不改變整個堆的情況下只更改一個節點的值時快速更新堆？我覺得這將是該計劃的一個巨大瓶頸。

Answer 1

首先是概念部分： 如果您使用堆插入方法的元素將其值減少爲插入的起點，而不是從集合的後面開始，那麼所有東西都可以正常工作。

我還沒有在C++中做過，但std :: push_heap看起來很好。