data-structures - 未排序的优先队列

Question

我被误导了一点，所以有点困惑。这就是我所理解的未排序优先级队列。有人可以确认吗？未排序的优先级队列是我们在最后插入并根据优先级（即队列中的最小值）删除元素的队列。

谢谢你。

Answer 1

优先级队列是一个抽象的数据结构，定义了get-min、push和pop-min方法，也可能是union。具体实现是否使用排序容器不应该影响我们应该能够执行的操作。

有几种可能的实现方式，其中最流行的是使用二进制堆（在某种程度上未排序），但一种方式也使用例如排序列表。我认为，无论您在哪里听说过unsorted priority queue此人，都可能意味着优先级队列，该队列未使用排序列表或其他排序容器实现。

Answer 2

数据结构中的基本队列基于先到先服务（FIFO）先进先出，第一个元素被插入队列中，一个将在队列中被服务或执行，最后一个元素将被最后服务或执行，此方法表示未排序的队列。

对于排序队列，它将对插入的元素进行排序，然后将它们作为排序方法执行

如果您添加了某种附加到队列的排序算法，它将像算法一样工作。更多信息： http: //en.wikipedia.org/wiki/Priority_queue
http://en.wikipedia.org/wiki/Sorting_algorithm

Answer 3

队列和优先级队列之间存在概念上的差异。队列是一种先进先出的数据结构，允许高效访问队列的两端（头和尾）。Priority Queue 是一种抽象数据结构，它提供 getBestItem() 函数，但没有具体说明如何（因此是abstract）。

Unsorted Priority Queue 可以指一种 PQ 实现，它不进行间歇性工作（不组织元素）并将 getBestItem() 实现为简单的线性搜索。这使得 getBestItem() 非常低效（O(n)），但插入/删除非常便宜（O(1)）。如果 Insert/Delete 频繁，而 getBestItem() 不是，这可能是一个有效的选择。