优先级队列

优先级队列是一种抽象数据类型概括了队列．它们的原理是完全相同的，除了它们还包括优先级对于队列中的每个值。当插入一个值时，将为它分配优先级。优先级最高的值总是首先被删除。

你可以把优先队列想象成一个医院。用先进先出(FIFO)的方法治疗病人并不总是一个好主意，因为有些病人可能处于危急状态。所以，一个咳嗽的病人可能会被分配到低优先级。之后可能会有枪伤的病人来，他们会被优先处理，然后先接受治疗。

优先级队列对于处理多个程序及其执行的系统(比如您的笔记本电脑)非常重要。它们对于像互联网这样的网络系统也非常重要，因为它们可以帮助确定重要数据的优先级，以确保数据更快地通过。

优先级队列有三种基本操作。

函数名*	提供的功能
插入(i, p)	增加价值我与优先级p．
pop ()	删除并返回优先级最高的元素。
peek ()	在不改变队列的情况下返回优先级最高的元素。

不需要确切的名字。事实上，某些功能可以由特定的语言直接通过特殊的语法提供。

下面的代码是python中优先级队列的实现。在一个有效的实现中，您可以期望为insert获得O(log n)的运行时(通过使用二进制搜索来查找它的放置位置)。不过，为了简单起见，我们还是用O(n)。

我们将使用整数分配优先级(整数越高，优先级越高)。此外，我们将在队列的字符串表示中显示优先级，以使练习更容易后来．

注意:Python有内置的实现优先队列和一个堆．

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

类PriorityQueue：def__init__（自我)：自我．qlist＝［］def插入（自我，我，p＝0)：如果len（自我．qlist）= =0：返回自我．qlist．附加（(我，p）)为x在范围（0，len（自我．qlist)):如果自我．qlist［x] [1］<p：返回自我．qlist．插入（x，（我，p）)返回自我．qlist．附加（(我，p）)def流行（自我)：如果len（自我．qlist）= =0：返回队列为空的返回自我．qlist．流行（0）def偷看（自我)：返回自我．qlist［0］def__repr__（自我)：返回str（自我．qlist）

让我们看看为什么这是一个糟糕的实现。的插入函数在一个堆取O(log n)因为它是二叉搜索树．然而，在这个实现中，我们必须潜在地检查中的每一个值self.qlist．这意味着我们的实现是O(n)插入．

让我们使用以上实施来处理进入医院的病人。当他们进来时，我们可以插入病人的名字、他们的病情和优先级。

1 2 3 4 5 6 7 8 9

>>>魁人党＝PriorityQueue（）>>>魁人党．插入（(“约翰。”，“流感”)，1）>>>魁人党．插入（(“莎莉”，“胳膊切”)，3.）>>>魁人党(((“莎莉”，“胳膊切”)，3.)，（(“约翰。”，“流感”)，1）]>>>魁人党．流行（）（(“莎莉”，“胳膊切”)，3.）>>>魁人党．流行（）（(“约翰。”，“流感”)，1）

所以即使我们把约翰在队列中，我们先放莎莉优先级更高，所以她先被pop ()函数。

让我们做一些关于优先队列的练习:

1)看一下实现代码以上特别是第7行和第8行。下面的输出是什么?

1 2 3 4

>>>魁人党＝PriorityQueue（）>>>魁人党．插入（“乔”，2）>>>魁人党．插入（“波利”，2）>>>魁人党．流行（）

这两个值,乔而且波利具有相同的优先级。谁先被处理?

如果您看一下实现中的第8行，您将看到我们向左扫描，直到找到一个优先级为的值少．如果我们找不到，我们就把它添加到列表中。因此，在这个实现中，如果有两个具有相同优先级的值，那么最先出现的值将最先出现。

1 2	>>>魁人党．流行（）（“乔”，2）

我们本可以选择相反的方式;我们只需要改变<第8行的运算到相等运算符＝．

2)在Python中，您可以比较多种类型的值，而不仅仅是整数。例如，您可以比较字符串。在Python中，将保持以下状态:

1 2

>>>“一个”<“b”真正的

那么，下面的输出是什么呢?

1 2 3 4

>>>魁人党＝PriorityQueue（）>>>魁人党．插入（“海登”，' d '）>>>魁人党．插入（“珍娜”，“米”）>>>魁人党．流行（）

正如我们上面看到的，在Python中，您可以比较字符串。的“一个”小于“b”．所以,“b”会有更高的优先级。的逻辑“米”优先级应该高于' d '．

1 2	>>>魁人党．流行（）（“珍娜”，“米”）

尽管我们在实现中使用了数组，但优先队列几乎总是使用某种类型的堆．优先队列是时间使用堆的复杂性是最常见的:

$\begin{array}{c}&\text{堆插入- O(log n)，} &\text{堆弹出- O(log n)，} &\text{堆Peek - O(1)}。结束\{数组}$

对于插入，我们可能不得不再次堆化整个数据结构。因此，虽然插入过程只需要O(1)个时间，但heapify过程需要O(log n)个时间。我们知道最大优先级值在哪里，但是重新创建堆仍然需要O(log n)时间。偷看，和其他的一样抽象数据类型，是一个常时间运算。

优先级队列用于如此多的不同领域，在这里列出它们是不切实际的。与它们的好处相比，它们引入的开销(优先级)通常是最小的。下面是一些使用优先级队列的例子:

1. 操作系统
   计算机中的操作系统管理哪些程序在什么时间执行。假设您的程序队列已满。突然，需要运行一个新的、非常重要的程序。您的操作系统将把它放在具有高优先级的队列中。

2. 图搜索算法
   许多高效的图搜索算法如*搜索而且迪杰斯特拉算法使用优先级队列来知道接下来要探索哪个节点。该应用程序还包括图搜索(如网络)的推论。

3. Time-activated事件
   如果一个程序有许多需要在不同时间执行的事件要执行，那么该程序可以使用优先队列。优先级将是执行程序的时间戳。然后队列将被正确排序。

4. 带宽管理
   队列用于处理因特网和其他网络上的数据流。然而，并不是所有的数据都同样重要。通过对重要数据进行优先排序，网络可以确保数据尽可能快地到达目的地。因此经常使用优先队列。