新的“堆” boost 库包括一个斐波那契堆。每个实现的复杂性可以在这里看到:http://www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structures.html .
我的问题是:为什么斐波那契堆减操作是O(log(N))，而增加操作是O(1)？
我想尝试在 Dijkstra 算法中使用斐波那契堆，该算法在很大程度上依赖于快速递减操作。
最佳答案
根据 http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html
boost.heap implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast to the typical textbook design, which uses min-heaps.
教科书/维基百科斐波那契堆具有最高优先级和最低值的元素，也称为最小堆(例如“1”的优先级高于“2”)。 STL 和 Boost(为了与 STL 保持一致)颠倒了定义，因此最高优先级具有最高值，也就是最大堆(即比“1”高“2”的优先级)。
本质上，这意味着 decrease 和 increase 在教科书和 Boost 之间具有相反的含义。
如果你想得到一个最小堆(如教科书定义)，你必须首先为你的 fibonacci_heap 定义一个合适的 boost::heap::compare 仿函数(请参阅此处的示例:Defining compare function for fibonacci heap in boost)，然后每当您减少与堆元素关联的值(并因此增加优先级)时调用 increase，反之亦然。
关于c++ - boost 斐波那契堆减操作，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12698431/