c++ - 提升斐波那契堆减少操作

Question

新的“堆”提升库包括一个斐波那契堆。每个实现的复杂性可以在这里看到：http: //www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structures.html。

我的问题是：为什么斐波那契堆减少操作是 O(log(N))，而增加操作是 O(1)？

我想尝试在 Dijkstra 算法中使用斐波那契堆，这在很大程度上依赖于快速减少操作。

Answer 1

根据http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html

boost.heap 将优先级队列实现为最大堆以与 STL 堆函数保持一致。这与使用最小堆的典型教科书设计形成对比。

教科书/维基百科斐波那契堆具有最高优先级元素和最低值，即最小堆（例如“1”优先级高于“2”）。STL 和 Boost（为了与 STL 保持一致）颠倒了定义，以便最高优先级具有最高值，也就是最大堆（即“2”优先级高于“1”）。

从本质上讲，它的意思是，decrease并且increase在教科书和 Boost 之间具有相反的含义。

如果您想获得一个最小堆（如教科书的定义），您必须首先boost::heap::compare为您定义一个适当的函子fibonacci_heap（参见此处的示例：在 boost 中为斐波那契堆定义比较函数increase），然后在您减少与相关联的值时调用一个堆元素（因此增加了优先级），反之亦然。