最常用的操作:FindMin。不太常见:Insert 和 ExtractMin。很少:删除节点。非常罕见:合并。
在列出的条件下，以下哪个优先级队列实际上更快？
- 基于排序双向链表的简单实现
- 简单堆
- 左派堆
- 二项式堆
- 斐波那契堆
- 2-3堆
- 配对堆
- 精简堆
- 厚堆
- 倾斜二项式堆
- 布罗达尔-冈崎队列
最佳答案
根据我五年多前所做的工作，我的经验是，在一般情况下，3 堆的性能优于二进制堆。跳过列表堆和配对堆的性能略优于 3 堆，但内存成本更高。上述所有三个指标均优于斐波那契堆。
Brodal队列理论上是最高效的。但是，正如布罗达尔本人所说，它们“相当复杂”并且“在实践中不适用”。 https://en.wikipedia.org/wiki/Brodal_queue
很多人谈论斐波那契堆效率，渐近分析表明它应该优于其他类型的堆。经验数据往往无法证明这一点。斐波那契堆有明显的缺点，如 https://en.wikipedia.org/wiki/Fibonacci_heap#Worst_case 中所述。 .
如果您想实现堆，我建议从二进制堆开始。或者是3堆，这是一个简单的优化。如果我需要更高的性能，我的下一步将是配对堆。它很容易实现并且非常高效。
除此之外，我没有任何建议。我在其他类型的堆上看到的性能数据并没有显示出明显的赢家。
关于data-structures - 实践中哪个优先级队列更快？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60117309/