关于优先级队列的性能，二叉堆、二项式堆、斐波那契堆
有人可以解释一下我应该如何决定是否使用标题中提到的一种或另一种堆实现吗？
我想要一个答案来指导我根据问题选择有关结构性能的实现。现在，我正在做一个优先级队列，但我不仅想知道这种情况下最合适的实现，而且想知道允许我在任何其他情况下选择实现的基础知识......
其他需要考虑的事情是这次我使用的是 haskell，所以，如果您知道任何可以改进这种语言的实现的技巧或东西，请告诉我！但和以前一样，也欢迎有关使用其他语言的评论！
谢谢！很抱歉，如果问题太基本，但我根本不熟悉堆。这是我第一次面临实施任务的任务......
再次感谢！
Could someone please explain me how should I decide whether to use one or another heap implementation, among the ones mentioned in the title?
I would like an answer to guide me on choosing the implementation regarding the performance of the structure, according to the problem. Right now, I'm doing a priority queue, but I would like to know not only the most appropriate implementation for this case, but the basics that allow me to choose an implementation in any other situation...
Other thing to consider is that I'm using haskell this time, so, if you know of any trick or something that would improve the implementation with this language, please let me know! but as before, comments about using other languages are welcome too!
Thanks! and sorry if the question is too basic, but i'm not familiar with heaps at all. This is the first time i'm facing the task of implementing one...
thanks again!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可能会在 http://themonadreader.files.wordpress.com/ 中找到第三篇文章2010/05/issue16.pdf 相关。
You might find the third article in http://themonadreader.files.wordpress.com/2010/05/issue16.pdf relevant.
首先，您不会在 Haskell 中实现标准堆。相反，您将实现一个持久性和功能性堆。有时，经典数据结构的函数版本与原始数据结构（例如简单的二叉树）一样具有性能，但有时则不然（例如简单的队列）。在后一种情况下，您将需要一个专门的函数数据结构。
如果您不熟悉函数式数据结构，我建议从 Okasaki 的伟大 书籍或论文 （感兴趣的章节：至少 6.2.2、7.2.2）。
如果您无法理解所有这些，我建议您从实现一个简单的链接二进制堆开始。 （在 Haskell 中创建一个高效的基于数组的二进制堆有点乏味。）一旦完成，您可以尝试使用 Okasaki 的伪代码甚至从头开始来实现二项式堆。
附言。 这个 cstheory.se 答案很棒
First of all, you won't be implementing a standard heap in Haskell. You'll instead be implementing a persistent and functional heap. Sometimes the functional versions of classical data structures are as performant as the original (e.g. simple binary trees) but sometimes not (e.g. simple queues). In the latter case you will need a specialized functional data structure.
If you are not familiar with functional data structures, I suggest starting with Okasaki's great book or thesis (chapters of interest: at least 6.2.2, 7.2.2).
If all of that went over your head, I suggest starting with implementing a simple linked binary heap. (Making an efficient array-based binary heap in Haskell is a bit tedious.) Once that is done, you could try your hand at implementing a binomial heap by using Okasaki's pseudo code or even starting from scratch.
PS. This cstheory.se answer is great
对函数式二项式堆、斐波那契堆和配对堆的一些参考：
https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
如果性能确实是问题所在，我建议使用配对堆。唯一的风险是它的性能到目前为止仍然是一个猜想。但实验表明，性能相当不错。
Some reference to functional Binomial heap, Fibonacci Heap and Pairing heap:
https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
If the performance is really the issue, I suggest using pairing heap. The only risk is that it's performance is still a conjecture till now. But experiments show that the performance is quite good.
它们对优先级队列的不同操作具有不同的时间复杂度。这是一个给你的可视化表格，
我从 普林斯顿大学讲座中获得了这张图片幻灯片
二叉堆：
二项式堆：
斐波那契堆：
注意：二项式和斐波那契堆看起来很熟悉，但它们有细微的不同：
They have different time complexity on different operations on Priority Queue. Here is a visual table for you
I got this image from the Princeton lecture slides
Binary Heap:
Binomial Heap:
Fibonacci Heap:
Note: Binomial and Fibonacci Heap looks familiar but they are subtly different: