我目前正在实现一些图形算法，并且想要一个具有斐波那契堆或宽松堆的复杂性的容器(特别是对于push和pop我至少希望O(logN)，对于reduce_key至少需要O(1))。
我不愿意在可能的情况下自己实现此目标(开发和测试开销以及时间)，并且我注意到Boost图形库在挂起的目录中引用了两个看起来很相似的数据结构。 Relax_heap.hpp中的轻松堆看起来很容易，但是我不太清楚如何使用它。它具有以下公共(public)功能(为清晰起见，对其进行了一些规定):
void push(const value_type& x);
value_type& top();
void pop();
哪些足够清楚，并实现我想要的推送和弹出。此外，还有:
void update(const value_type& x);
void remove(const value_type& x);
我想我可以使用update来实现reduce_key，但是我不清楚如何实现。我的特殊问题是，我假设该值是在调用push时复制的。我觉得我需要的是一个指向堆中值副本的指针，这样我就可以通过引用对其进行修改，然后调用update将其改回其所属位置。但是，这样的指针似乎不可用？
总体上有轻松堆经验的人，或者特别愿意增加轻松堆经验的人，愿意通过解释或漂亮的代码片段使我摆脱痛苦吗？
谢谢，
亚历克斯
最佳答案
亚历克斯
如果您 check out /下载/浏览Boost库，则有一个libs / graph / test目录。测试之一是relaxed_heap_test.cpp，它似乎涵盖了更新成员函数。
-s-