提升斐波那契堆的降低操作能力

Question

提升斐波那契堆的降低操作能力

c++boostheapfibonacci-heap

4

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

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

我想尝试在Dijkstra算法中使用斐波那契堆，Dijkstra算法在快速减少操作方面非常依赖。

- user1487088

阅读维基百科文章：http://en.wikipedia.org/wiki/Fibonacci_heap - Keith Randall

维基百科文章只谈到了减少键的摊销O(1)。 - user1487088

嗯，维基百科文章（它是一个最小堆）和Boost库（它是一个最大堆）之间交换了min和max。要使用Boost库进行Dijkstra算法，您必须反转分数比较。 - Keith Randall

好的，我将“增加”解释为将元素推向堆顶，而“减少”则是将元素推离堆顶。无论堆顶是最小值还是最大值，都没有关系，对吗？这正确吗？ - user1487088

因此，根据您的解释，增加操作的平摊复杂度为O(1) - 这是Fibonacci堆的基本优势。由于所有其他标准堆操作都具有该复杂度（您可以使用删除+插入实现减少操作），因此减少操作的复杂度为O(log n)。 - Keith Randall

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ɲeuroburɳ · Accepted Answer

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

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

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

本质上，这意味着在教材和Boost之间，“减少”和“增加”的含义相反。

如果你想得到一个小根堆（就像教科书中的定义），你必须首先为你的 fibonacci_heap 定义一个适当的 boost::heap::compare 函数对象（参见此处示例：Defining compare function for fibonacci heap in boost），然后在你减少与堆元素相关联的值（从而增加优先级）时调用 increase，反之亦然。