新的“堆”增强库包括斐波那契堆。每个实现的复杂性可以在这里看到：http://www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structs.html 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 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 and increase教科书和Boost之间的含义相反。
如果你想获得一个最小堆（如教科书定义），你必须首先定义一个适当的boost::heap::compare函子为你的fibonacci_heap（参见此处的示例：在boost中定义斐波那契堆的比较函数 https://stackoverflow.com/questions/16705894/defining-compare-function-for-fibonacci-heap-in-boost），然后调用increase每当您减少与堆元素关联的值（从而增加优先级）时，反之亦然。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
