关于优先级队列的性能，二进制堆vs二项式堆vs fibonacci堆

Question

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

根据问题，我想要一个答案来指导我选择有关结构性能的实施方案。现在，我正在做一个优先级队列，但我想知道这个案例最合适的实现，但是基本允许我在任何其他情况下选择一个实现...

其他需要考虑的事情是我这次使用的是haskell，所以，如果你知道任何可以用这种语言改进实现的技巧或其他东西，请告诉我！但和以前一样，欢迎使用其他语言的评论！

谢谢！对不起，如果问题太基础，但我根本不熟悉。这是我第一次面临实施一项任务的任务......

再次感谢！

Answer 1

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

Answer 2

首先，您不会在Haskell中实现标准堆。您将改为实现持久且功能性的堆。有时，经典数据结构的功能版本与原始数据结构一样（例如简单的二叉树），但有时不符合（例如简单的队列）。在后一种情况下，您将需要一个专门的功能数据结构。

如果您不熟悉功能数据结构，我建议从Okasaki的伟大的book或thesis开始（感兴趣的章节：至少6.2.2,7.2.2）。

---

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

PS。 This cstheory.se answer is great

Answer 3

它们在优先级队列上的不同操作上具有不同的时间复杂度。这是一个可视化的桌子

╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║  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)    ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║             
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝

我从Princeton lecture slides得到了这个图像

二进制堆：

---

二项式堆：

---

斐波纳契堆：

注意：二项式和斐波纳契堆看起来很熟悉，但它们略有不同：

• 二项堆：每次插入后急切地合并树。
• Fibonacci堆：懒惰推迟合并，直到下一个delete-min。

Answer 4

一些参考功能二项式堆，Fibonacci堆和配对堆：https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf

如果性能确实是问题，我建议使用配对堆。唯一的风险是它的表现至今仍然是一个猜想。但实验表明，性能非常好。