标签: fibonacci-heap

有没有人曾经实施过Fibonacci-Heap？几年前我这样做了,但它比使用基于阵列的BinHeaps要慢几个数量级.

那时候,我认为这是一个很有价值的教训,研究的结果并不像它声称的那样好.然而,许多研究论文声称他们的算法的运行时间基于使用Fibonacci-Heap.

你有没有设法产生有效的实施？或者你使用的数据集如此之大,以至于Fibonacci-Heap效率更高？如果是这样,一些细节将不胜感激.

我已经阅读了有关Fibonacci堆的维基百科文章,并阅读了CLRS对数据结构的描述,但它们对于这种数据结构的工作原理几乎没有直觉.为什么Fibonacci堆的设计方式如何呢？他们是如何工作的？

谢谢!

Fibonacci堆和二进制堆的真实世界应用是什么？如果你可以在用它来解决问题时分享一些实例,那就太棒了.

编辑:还添加了二进制堆.很想知道.

我正在研究不同类型的堆数据结构.

Fibonacci堆似乎具有更好的最坏情况复杂度(1)插入,(2)删除和(2)找到最小元素.

我发现在Java中有一个类PriorityQueue是平衡的二进制堆.但为什么他们不使用Fibonacci堆？

另外,是否有斐波那契堆的实现java.util？

谢谢!

我知道Prim的算法,我知道它的实现,但我总是跳过一个我想问的部分.有人写道,Prim与Fibonacci堆的算法实现是O(E + V log(V)),我的问题是:

• 什么是斐波纳契堆？
• 它是如何实现的？和
• 如何用Fibonacci堆实现Prim的算法？

的斐波那契堆数据结构在其名称中的"黄金分割",但没有在数据结构似乎使用斐波那契数.根据维基百科的文章:

Fibonacci堆的名称来自Fibonacci数字,用于运行时间分析.

Fibonacci堆中如何出现这些Fibonacci数？

Fibonacci堆在实践中用于任何地方吗？我环顾四周,找到了相关问题的答案(见下文),但实际上并没有回答这个问题.

1. Fibonacci有很好的实现,包括标准库,如Boost C++.这些库包含Fibonacci堆的事实表明它们必须在某个地方有用.
2. 我们知道Fibonacci堆在实践中需要满足某些条件:" 要在实践中受益于Fibonacci堆,你必须在reduce_keys非常频繁的应用程序中使用它们 "; " 为了使Fibonacci Heap真正发光,您需要以下两种情况之一:a)昂贵的比较:Fib Heaps最小化组织数据所需的比较次数.b)大多数操作是updateKey/insert/delete.作为Fibonacci堆叠将这些更新"组合"到下一个extractMin,"批次"越大,它获得的效率就越高. "
3. 有一个称为"Brodal Queue"的数据结构,我不确定之前我听说过它似乎有时间复杂性行为至少与Fibonacci堆一样好. 这是一个很好的表格,比较了不同种类堆的各种操作的时间复杂性.
4. 在关于是否有斐波那契的任何应用程序问题或二项堆,应答者只给了二项堆的例子.

我正在从"引入算法"学习f-heap,而'减少键'操作确实让我感到困惑 - 为什么这需要'级联切换'？

如果删除此操作:

1. make-heap(),insert(),minimum()和union()的成本显然保持不变
2. extract-min()仍然是O(D(n)),因为在O(n(H))'合并'操作中,大多数有根树的成本可以在它们被添加到根列表时支付,并且剩余成本O(D(n))
3. decrease-key():显然是O(1)

至于D(n),虽然我不能准确地解释它,我认为它仍然是O(lgn),因为没有'cascading-cut',一个节点可能稍后被移动到根列表,并且任何节点隐藏在父亲之下不会影响效率.至少,这不会使情况变得更糟.

为我可怜的英语道歉:(

谁有人可以帮忙？谢谢

是否有可用于Haskell的Fibonacci堆/优先级队列？(或者甚至是渐近更好的一个？)我在这个问题中找到了各种优先级队列实现的列表,但我找不到它们是否满足Fibonacci堆的摊销运行时间:

• Find-minimum是O(1)摊销时间.
• 操作插入,减少键和合并(联合)工作是O(1)摊销时间.
• 操作删除和删除最小值是O(log n)分摊的时间.

参见理论界限的比较.

我有兴趣实现一个优先级队列,以实现一个相对简单的高效Astar实现(我的意思是优先级队列很简单).

似乎因为Skip List提供了一个简单的O(1)extract-Min操作和一个O(Log N)的插入操作,它可能与更难实现的具有O(log N)提取的Fibonacci Heap竞争 - 最小和O(1)插入.我认为Skip-List对于具有稀疏节点的图更好,而Fibonacci堆对于具有更密集连接的节点的环境更好.

这可能会使Fibonacci Heap通常更好,但我认为Big-Oh明智的这些是相似的吗？