reheapify的STL实现
在图算法中，我需要找到具有最小值的节点。
在算法的一个步骤中，可以减少该节点或其邻居的值，并且可以根据其值删除其一些邻居。 另外，我不想每次都在整个图中搜索该节点（尽管它不是那么大（<1000 个节点））。
因此我查看了STL库，发现堆结构几乎可以满足我的要求。我可以非常快地插入和删除节点，但是当我只更改一个节点的值而不使用整个堆时，有没有一种方法可以快速更新堆？我觉得这将是该计划的一个巨大瓶颈。
In a graph algorithm, I need to find the node with the smallest value.
In a step of the algorithm the value of this node or its neighbors can be decreased and a few of its neightbors can be removed dependent on their value.
Also, I don't want to search the whole graph for this node each time (although it is not so big (<1000 nodes)).
Therefore I looked at the STL library and found the heap structure which almost does what I want. I can insert and delete nodes very fast, but is there a method to update the heap fast when I only changed the value of one node without resorting the whole heap? I feel it would be a huge bottleneck in the program.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先是概念部分：
如果您使用堆插入方法，将减少其值的元素作为插入的起点，而不是从集合的后面开始，那么一切都会正常工作。
我还没有在 C++ 中这样做过，但是 std::push_heap 看起来很适合这个目的。
First the conceptual part:
If you use the heap insertion method with the element that decreased it's value as the starting point for insertion instead of starting at the back of the collection everything just works.
I haven't done that in C++ yet, but std::push_heap looks fine for that purpose.