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

Question

我知道最小堆和最大堆的工作原理，但对什么是优先级队列及其区别感到困惑。任何帮助将不胜感激。

Answer 1

Priority queue是定义三个操作的抽象数据类型(接口(interface)定义):is_empty、insert_with_priority 和pull_highest_priority_element。该定义说明了这些功能的作用，但没有说明如何实现。

A binary heap是实现优先级队列的一种方法。它的优点是易于实现并且效率相当高。它不一定是实现优先级队列的最有效方法(见下文)。堆肯定是优先级队列，但优先级队列绝不是堆。

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

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

有许多称为“堆”的优先级队列实现，但它们与传统的二叉堆共享的共同点很少。 Pairing heap ，例如，理论上比二进制堆更有效，Fibonacci heap 也是如此。 .在实践中，配对堆效率更高，但斐波那契堆不是。和 Brodal queue被证明在理论上是最有效的，但它很难实现，而且在实践中比其他优先级队列实现要慢得多。

您还可以使用 Skip list 实现优先级队列.我的经验是，跳跃列表优先级队列与二进制堆一样快，有时甚至快得多。

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