algorithm - 什么时候为优先队列使用堆是个坏主意？

Question

在 Cormen 等人的《算法简介》一书中解释 Dijkstra 算法的部分中。等，在分析算法的复杂性时，他们说

如果图足够稀疏......我们可以通过使用二进制最小堆实现最小优先级队列来改进算法

所以我想知道，这样的声明有什么必要？将堆用于优先级队列不是更明智吗？

Answer 1

有许多不同的方法来实现优先级队列。二进制最小堆很有用，因为它性能相当好并且易于实现。但是配对堆也很容易实现，并且对于某些操作具有更好的性能。特别是，它比二叉堆更快地执行减少键操作。

或者您可以使用跳过列表优先级队列。跳过列表有一些很好的属性，使其在某些优先队列应用程序中很有吸引力。特别是，创建并发跳过列表比并发堆更容易。

所以，不，将堆用于优先级队列并不总是更明智。几乎可以肯定，使用堆比使用排序列表更明智，但有时其他东西比堆更合适。

Answer 2

见https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

它说：

• Dijkstra 的原始算法不使用最小优先级队列并且在 O(|V|^2) 中运行。

所以书里的说法只是说可以优化原算法。

• 基于由斐波那契堆实现并在 O(|E|+|V|log|V|) 中运行（其中 |E| 是边数）的最小优先级队列的实现是由于（Fredman & Tarjan 1984 ）。

二叉堆只是堆的一种。还有其他类型更适合特定场景。