新的“堆” Boost库包括一个斐波那契堆。 每个实施的复杂性可以在这里看到： 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实现优先级队列为max-堆是与STL堆函数相一致。 这与典型的教科书设计，它使用最小堆。
教科书/维基百科斐波纳契堆具有最低值的最高优先级的元素，也叫做最小堆（例如，“1”是大于“2”的优先级更高）。 STL和Boost（与STL稠度）扭转的定义，以使最高优先级的具有最高的值，也称为一个最大堆（即，“2”高于“1”的优先级）。
本质上，它意味着decrease和increase有课本和升压之间的逆含义。
如果你想获得一个最小堆（如教科书的定义），您必须首先定义一个适当boost::heap::compare仿函数为您fibonacci_heap （这里看一个例子： 定义比较功能的升压斐波那契堆 ），然后叫increase每当你降低与堆元件相关联的值（并且因此增加了优先级），并且反之亦然。
文章来源: Boost Fibonacci Heap Decrease Operation
