有没有基于Fibonacci堆的Haskell优先队列？

Question

是否有可用于Haskell的Fibonacci堆/优先队列？（或者甚至是渐近更好的一种？）我在这个问题中找到了各种不同的优先队列实现列表，但我无法确定它们中的任何一个是否满足Fibonacci堆的摊销运行时间要求：

• 查找最小值摊销时间为O(1)。
• 插入、减少键和合并（联合）操作的摊销时间为O(1)。
• 删除和删除最小值操作的摊销时间为O(log n)。

请参见理论边界比较。

- Petr

---

可能不存在生产代码，因为常数因子通常使得斐波那契堆在合理大小的数据集上比二项堆慢，尽管在理论上有渐近优势。 - Oliver Charlesworth

@OliCharlesworth 很有趣，你能大概估算一下在什么规模情况下斐波那契堆变得更加优势吗？ - Petr

说实话，这有点超出了我的领域；我只是读过一些关于这种缺点的资料（例如参见CLRS）。不要引用我的话 ;) - Oliver Charlesworth

http://hackage.haskell.org/package/pqueue 是相当优化的。 - Louis Wasserman

Answer 1

虽然不是斐波那契堆，但同样优秀的替代品是heaps，它是由Edward Kmett开发的，基于Brodal堆的持久化变种。

- Philip JF

---

E. Kmett 没有实现的东西实际上有吗？ - Petr