优先级队列和最小/最大堆有什么区别？

Question

我知道最小和最大堆的工作方式，但是对于优先级队列是什么以及它有何不同感到困惑。任何帮助将不胜感激。

Answer 1

优先级队列是一种抽象数据类型（接口定义），它定义了三个操作：is_empty，insert_with_priority和pull_highest_priority_element。该定义说明了这些功能应该做什么，但没有说明如何实现。

一个二元堆是实现优先级队列的一种方式。它的优点是易于实施并且相当有效。这不一定是实现优先级队列的最有效方法（请参见下文）。尽管堆绝对是优先级队列，但优先级队列绝对不是堆。

堆通常实现的功能比优先级队列所需的功能更多。例如，堆通常具有一个构造器，该构造器将非常快速地构建内部数据结构，而不必为每个项目调用insert方法。堆通常还实现一个peek方法，该方法将返回第一项而不删除它。这两个功能都不是优先级队列定义的一部分。

您可以使用简单的未排序列表实现优先级队列，但是这样做并不是特别有效。与排序列表相同。您还可以使用平衡的二进制搜索树，该树将为您提供比列表更好的性能，但不如二进制堆好。

有许多优先级队列实现称为“堆”，但它们与传统二进制堆的共享点很少。例如，配对堆在理论上比二进制堆（斐波那契堆）更有效。在实践中，配对堆是更有效，但斐波那契堆是没有的。并且Brodal队列在理论上被证明是最大效率的，但是它比其他优先级队列的实现难于实现，并且在实践中要慢得多。

您还可以使用“ 跳过列表”实现优先级队列。我的经验是，跳过列表优先级队列的速度与二进制堆一样快，有时甚至快于二进制堆。

优先级队列数据结构有许多不同的实现。您可以在https://en.wikipedia.org/wiki/Heap_(data_structure)#Variants中找到部分列表。