c++ - 帮助使用 boost relaxed heap

Question

我目前正在实现一些图形算法，我想要一个具有斐波那契堆或松弛堆复杂性的容器(具体来说，我想要至少 O(logN) 用于推送和弹出，O(1) 用于reduce_key)。

如果可能的话(开发和测试的开销和时间)，我并不热衷于自己实现它，并且我注意到 boost 图形库在挂起目录中引用了几个看起来可能的数据结构。 relaxed_heap.hpp 中的 relaxed heap 看起来很合适，但我不太清楚如何使用它。它具有以下公共(public)功能(为清楚起见，精确了一点):

void push(const value_type& x);
value_type& top();
void pop();

哪些足够清楚并实现我想要的推送和弹出。此外还有:

void update(const value_type& x);
void remove(const value_type& x);

我假设我可以使用更新实现 reduce_key，但我不清楚如何实现。我的特殊问题是我假设在调用 push 时复制了该值。我觉得我需要的是一个指向堆中值拷贝的指针，这样我就可以通过引用修改它，然后调用 update 将它改组回它所属的位置。不过好像没有这样的指针？

有没有大体上有松弛堆使用经验，或者特别是 boost 松弛堆的人愿意通过解释或漂亮的代码片段让我摆脱痛苦？

谢谢，

亚历克斯

Answer 1

亚历克斯， 如果您 checkout /下载/浏览 boost 库，则会有一个 libs/graph/test 目录。其中一项测试是 relaxed_heap_test.cpp，它似乎覆盖了更新成员函数。

-s-