升压斐波那契堆减少操作 [英] Boost Fibonacci Heap Decrease Operation
问题描述
新的'堆'Boost库包括一个斐波那契堆。每个实现的复杂性可以在这里看到：的http：/ /www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structures.html 。
The new 'heap' boost library includes a fibonacci heap. The complexity of each implementation can be seen here: http://www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structures.html.
我的问题是：为什么斐波那契堆减少操作为O（log（N）），而增加操作O（1）？
My question is this: Why is the fibonacci heap decrease operation O(log(N)), while the increase operation is O(1)?
我想在Dijkstra算法，这在很大程度上依赖于一个快速下降的操作使用斐波那契堆进行试验。
I would like to experiment with using the fibonacci heap in Dijkstra's algorithm, which is heavily dependent upon a fast decrease operation.
推荐答案
据的 http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html
boost.heap实现优先级队列为max-堆以与STL堆函数一致。这是相对于典型的教科书设计，它使用最小堆。
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的一致性）扭转定义，以便最高优先级具有最高的价值，又名一个最大堆（即不是12更高的优先级）。
The textbook/wikipedia Fibonacci heap has the highest priority element with the lowest value, aka a min-heap (e.g. "1" is higher priority than "2"). STL and Boost (for consistency with STL) reverse the definition so that the highest priority has the highest value, aka a max-heap (i.e. a "2" higher priority than "1").
本质上，它意味着减少和增加有课本和升压之间的逆含义。
Essentially it means that decrease and increase have inverse meanings between textbook and Boost.
如果你想获得一个最小堆（如教科书的定义），您必须首先定义一个适当的的boost ::堆::比较仿函数为你的 fibonacci_heap （在这里看到一个例子：<一href=\"http://stackoverflow.com/questions/16705894/defining-compare-function-for-fibonacci-heap-in-boost\">Defining比较在升压斐波那契堆功能），然后调用增加当你降低与堆元素相关的值（并因此提高优先级）和副反之亦然。
If you want to get a min-heap (like the textbook definitions), you must first defined an appropriate boost::heap::compare functor for your fibonacci_heap (see an example here: Defining compare function for fibonacci heap in boost), then call increase whenever you decrease the value associated with a heap element (and are thus increasing the priority) and vice-versa.
这篇关于升压斐波那契堆减少操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
