未排序优先级队列

Question

我已经被误导了一点，所以我有点confused.This是什么，我已经理解为一个未排序的优先级，有人能确认一下吗？未排序的优先级队列是指根据优先级(即队列中的最小值)在队列末尾插入和删除元素的队列。

谢谢。

Answer 1

数据结构中的基本队列是先来先服务(FIFO)，第一个元素插入队列中，一个元素在队列中被服务或执行，最后一个元素在队列中被服务或执行，这种方法代表了无序队列。

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

如果您在队列中添加了某种排序算法，它将像算法一样工作。有关更多信息，请访问：http://en.wikipedia.org/wiki/Priority_queue

http://en.wikipedia.org/wiki/Sorting_algorithm

Answer 2

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

有几种可能的实现，其中最流行的使用二进制堆(在某种程度上是不排序的)，但也有一种方法使用排序列表。我想，无论您在哪里听说过unsorted priority queue，这个人可能指的是一个优先级队列，它不是使用排序列表或其他排序容器实现的。

Answer 3

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

未排序的优先级队列可以指不做间歇性工作(不对元素进行组织)并将getBestItem()实现为简单的线性搜索的PQ实现。这使得getBestItem()非常低效(O(n))，但是插入/删除非常便宜(O(1))。如果频繁插入/删除，而getBestItem()不频繁，这可能是一个有效的选择。