二叉堆 vs 二项式堆 vs 斐波那契堆，关于优先队列性能的比较。

Question

请问有人能解释一下，我应该如何决定在标题中提到的堆实现中使用哪一个?

我希望得到一个回答，指导我在根据问题需要选择结构的性能方面选择实现。目前，我正在进行优先队列，但我想知道不仅在此情况下最适合的实现方式，还要了解基本原理，使我可以在任何其他情况下选择实现方式...

另一个需要考虑的东西是，这次我正在使用Haskell，因此，如果您知道任何技巧或可以改善此语言的实现的内容，请告诉我！但是和之前一样，关于使用其他语言的评论也是可以接受的！

谢谢！如果问题太基础了，对不起，但我对堆完全不熟悉。这是我第一次面临实施堆任务...

再次感谢！

- Throoze

---

嗯，如果这是你第一次实现一个堆，就先编写一个使用二叉堆的版本。只需将其抽象化，以便能够在必要时替换为其他内容。二项式堆和斐波那契堆比二叉堆复杂得多，可能不值得费力（除非你只想学习它们）。 - Tikhon Jelvis

将它们全部实现并使用您的应用程序进行基准测试。 - augustss

请查看这篇文章，它列出了不同的时间。你会发现二叉堆也符合你的约束条件。由于二叉堆更简单、更优雅，我建议使用它，即使其他数据结构可能具有更好的性能。 - Tikhon Jelvis

可能想看看这些内容：二叉堆和二项堆有什么区别？、何时使用二项堆？、斐波那契堆数据结构的直觉是什么？、二叉堆和斐波那契堆的现实应用、纯函数式语言中高效的堆。 - nawfal

可能是纯函数语言中高效堆的实现的重复问题。 - Ciro Santilli OurBigBook.com

Answer 1

您可能会发现http://themonadreader.files.wordpress.com/2010/05/issue16.pdf中的第三篇文章相关。

- Louis Wasserman

---

在第三篇文章的第45页上，当他们定义 data Succ rk a = BinomTree rk a ? rk a 时，第二个 rk a 前面有一个有趣的符号，像一个倒三角形（而不是我写的 '?' 符号）... 我不太熟悉 Haskell 语法，请问这个符号是什么意思？谢谢！ - Throoze

@Throoze: 奇怪的三角形只是类型Succ的中缀数据构造器。您可以将该行读作：data Succ rk a = Succ (BinomTree rk a) (rk a)。 - opqdonut

这只是一个符号，使纸张更易读。在编写实际程序时，我通常会写中缀构造函数“:<:”。opqdonut的解释也可以。 - Louis Wasserman

（另外，完全公开：我是那篇文章的作者。） - Louis Wasserman

Answer 2

首先，你不会在Haskell中实现标准堆。相反，你将会实现一个持久化的和函数式的堆。有时候，类似于经典数据结构的函数式版本与原始版本的性能一样好（例如简单的二叉树），但有时候不是（例如简单队列）。在后一种情况下，你需要一个专门的函数式数据结构。

如果你不熟悉函数式数据结构，我建议从Okasaki's greatbook或thesis开始学习（感兴趣的章节至少包括6.2.2、7.2.2）。

---

如果你对上述内容感到困惑，我建议从实现一个简单的链接二叉堆开始。(在Haskell中制作一个高效的基于数组的二叉堆有点繁琐。)一旦完成了这个，你可以尝试使用Okasaki的伪代码或甚至从头开始实现二项堆。

附注：这个cstheory.se的答案很棒

- opqdonut

Answer 3

一些关于功能二项堆、斐波那契堆和配对堆的参考资料： https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

如果性能真的是问题，我建议使用配对堆。唯一的风险是它的性能仍然是一个猜想。但实验表明，性能相当不错。

- Larry LIU Xinyu

Answer 4

它们在优先队列的不同操作上具有不同的时间复杂度。这里是一个可视化表格供您参考

╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║  Operation   ║       Binary          ║      Binomial          ║       Fibonacci              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║   insert     ║      O(logN)          ║      O(logN)           ║         O(1)                 ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║  find Min    ║       O(1)            ║      O(logN)           ║         O(1)                 ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║   Revmove    ║       O(logN)         ║      O(logN)           ║        O(logN)               ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║ Decrease Key ║       O(logN)         ║      O(logN)           ║        O(1)                  ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║    Union     ║         O(N)          ║      O(logN)           ║        O(1)                  ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║ ■ Min element is root ║order k binomial tree Bk║ ■ Set of heap-ordered trees. ║
║              ║ ■ Heap height = logN  ║ ■ Number of nodes = 2k.║ ■ Maintain pointer to min.   ║
║              ║                       ║ ■ Height = k.          ║   (keeps find min/max O(1))  ║                        
║              ║                       ║ ■ Degree of root = k.  ║ ■ Set of marked nodes.       ║
║  Useful      ║                       ║ ■ Deleting root yields ║   (keep the heaps flat)      ║
║  Properties  ║                       ║   binomial trees       ║                              ║
║              ║                       ║   Bk-1, … , B0.        ║                              ║
║              ║                       ║   (see graph below)    ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║             
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝

我从普林斯顿讲义幻灯片中获取了这张图片。

二叉堆：

---

二项堆：

---

斐波那契堆：

注意：二项堆和斐波那契堆看起来很相似，但它们有微妙的区别：

- 二项堆：每次插入后都会急切地合并树。 - 斐波那契堆：懒惰地推迟合并，直到下一个删除最小值操作。

- OLIVER.KOO