二进制堆与二项式堆与斐波那契堆，关于优先级队列的性能

Question

有人可以解释一下标题中提到的那些实现中，我该如何决定使用一个或另一个堆实现？

我想要一个答案来指导我根据问题选择关于结构性能的实现。现在，我正在做一个优先级队列，但是我不仅想知道这种情况下最合适的实现，而且还想知道可以在任何其他情况下选择实现的基础知识。

要考虑的另一件事是这次我正在使用haskell，因此，如果您知道任何技巧或可以改善这种语言实现的东西，请告诉我！但是像以前一样，也欢迎使用其他语言的评论！

谢谢！很抱歉，如果这个问题太基本了，但是我一点都不熟悉堆。这是我第一次面临实施任务的任务。

再次感谢！

Answer 1

您可能会在 http：//themonadreader.files.wordpress中找到第三篇文章.com / 2010/05 / issue16.pdf 相关。

Answer 2

首先，您将不会在Haskell中实现标准堆。相反，您将实现一个 persistent 和 functional 堆。有时经典数据结构的功能版本与原始版本（例如简单的二叉树）一样性能好，但有时却没有（例如简单队列）。在后一种情况下，您将需要专门的功能数据结构。

如果您不熟悉功能数据结构，建议从Okasaki出色的本书或论文（兴趣：至少6.2.2、7.2.2）。

---

如果所有这些都超出了您的范围，我建议从实现一个简单的 linked 二进制堆开始。 （在Haskell中创建高效的基于数组的二进制堆有点乏味。）完成之后，您可以尝试使用Okasaki的伪代码甚至从头开始实现二项式堆。

PS。 此cstheory.se答案很好

Answer 3

在优先级队列上的不同操作上，它们具有不同的时间复杂度。这是适合您的可视表 通用标签

我从普林斯顿讲义幻灯片

二进制堆：

---

二项式堆：

---

斐波那契堆：

注意：二项式和斐波那契堆看起来很熟悉，但是它们有细微的差别：

• 二项式堆：每次插入后都急于合并树。
• 斐波纳契堆：延迟将合并推迟到下一个删除分钟。

Answer 4

对功能二项式堆，斐波那契堆和配对堆的一些引用： https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

如果性能确实是问题，我建议使用配对堆。唯一的风险是，到目前为止，它的性能仍然是一个推测。但是实验表明，它的性能还不错。