在图算法中，我需要找到具有最小值的节点。
在算法的一个步骤中，可以减少该节点或其邻居的值，并且可以根据它们的值删除它的一些邻居。 另外，我不想每次都在整个图中搜索这个节点(虽然它不是很大(<1000 个节点))。
因此我查看了 STL 库并找到了几乎可以满足我要求的堆结构。我可以非常快速地插入和删除节点，但是当我只更改一个节点的值而不诉诸整个堆时，有没有一种方法可以快速更新堆？我觉得这将是程序中的一个巨大瓶颈。
最佳答案
首先是概念部分: 如果您将堆插入方法与减少它的值的元素一起用作插入的起点，而不是从集合的后面开始，一切都会正常进行。
我还没有用 C++ 做到这一点，但 std::push_heap 看起来很适合这个目的。
关于c++ - reheapify的STL实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9189402/