打破平局
当存在具有相同优先级的元素时，会发生绑定优先级队列。
当两个元素不可比较时，即比较器在比较队列的 a 和 b 元素后返回 0。
在这种情况下，优先级队列必须决定哪个元素将首先出队。
这就是打破平局（Tie breaking）。
如果出现平局，我们可以在优先级队列中实现 FIFO（先进先出）或者 LIFO（后进先出）。
反转优先级队列顺序
要反转优先级队列的顺序，请使用 sorted() 方法对队列进行排序并将 reverse 参数设置为 True。
默认情况下，队列按升序排序。
如果 reverse 参数设置为 true，它将按降序更改序列，如下例所示：
代码：
import heapq heap = [] heapq.heappush(heap, (3, "Africa")) heapq.heappush(heap, (1, "America")) heapq.heappush(heap, (2, "Asia")) heapq.heappush(heap, (4, "Europe")) print(sorted(heap, reverse=True))
删除一个元素
要从优先队列中删除元素，我们只需弹出该元素即可。
具有最高优先级的元素将出队并从队列中删除。
创建队列：
代码：
import heapq hq = [] heapq.heappush(hq, (3, "Jean")) heapq.heappush(hq, (2, "Eric")) heapq.heappush(hq, (4, "Monica")) heapq.heappush(hq, (1, "oiry")) heapq.heappop(hq)
带有自定义比较器的Python优先级队列
自定义比较器用于比较两个用户定义的可迭代对象。
在 Python Priority Queue 中，可以使用自定义比较器根据用户定义的值对队列进行排序。
例如，我们使用 heapq 创建一个优先级队列。
然后我们使用 sorted() 方法对 heapq 进行排序。
它将根据元素的键（优先级编号）对队列中的元素进行排序。
考虑下面的例子：
代码：
import heapq heap = [] heapq.heappush(heap, (3, "eat")) heapq.heappush(heap, (1, "study")) heapq.heappush(heap, (2, "rest")) heapq.heappush(heap, (4, "sleep")) print(sorted(heap))
现在让我们根据自定义比较器对队列进行排序。
我们希望以这样一种方式排列队列中的元素，即在对队列进行排序后，值按字母顺序排列。
为此，我们将使用 lambda 函数。
一个 lambda 函数是一个小的匿名函数，它由一个带有任意数量参数的表达式组成。
lambda 函数或者 lambda 表达式返回一个可以在程序中的任何地方使用的值。
代码：
import heapq heap = [] heapq.heappush(heap, (3, "eat")) heapq.heappush(heap, (1, "study")) heapq.heappush(heap, (2, "rest")) heapq.heappush(heap, (4, "sleep")) print(sorted(heap, key=lambda heap: heap[1]))
在此示例中，lambda 表达式告诉按字母顺序根据值（而不是键）对队列进行排序。
sorted() 方法接受三个参数：
- 可迭代的：要排序的序列
- 键：键是可选的。它被认为是排序比较的基础。关键是用户定义的比较器函数。
- Reverse ：Reverse 是一个布尔值。如果它设置为true，它将反转排序的序列。 reverse 参数默认为 false 意味着它将按升序对序列进行排序。如果 reverse 设置为 true，则序列将按降序排列。
如何在 Python 中创建优先队列？
Priority Queue 中的元素始终包含一个键和一个值。
键量化了元素的优先级。
使用列表：
使用列表实现优先队列非常简单。
只需创建一个列表，添加元素（键，值），并在每次添加元素时对列表进行排序。
代码：
employees = []
employees.append((1, "Andrew"))
employees.append((4, "John"))
employees.sort(reverse = True)
employees.append((3, "Jean"))
employees.sort(reverse = True)
employees.append((2, "Matt"))
employees.sort(reverse = True)
while employees:
print(employees.pop())
当第一个元素被追加到列表中时，不需要对列表进行排序。
优先队列的列表实现效率不高，因为列表需要在每个新条目之后进行排序。
因此，根据元素的优先级维护元素的顺序需要时间。
使用元组
Python 元组和列表在某种程度上是相同的。
列表和元组都是 Python 的有序数据结构，并且允许重复值。
但是列表的元素是可变的，而元组的元素是不可改变的。
要使用元组实现优先队列，我们将首先使用优先队列的元素创建一个元组，然后对元组进行排序。
由于我们无法更改元组中的元素，因此元组不提供像列表一样的常规排序功能。
要对元组进行排序，我们需要使用 sorted 函数。
sort 和 sorted 方法之间的区别在于 sort 方法不返回任何内容，而是对列表的实际序列进行更改。
而 sorted 函数始终返回已排序的序列，并且不会干扰元组的实际序列。
在以下代码行中，我们将创建一个元组并使用元组实现优先级队列：
mytuple = ((1, "bread"), (3, "pizza"), (2, "apple"))
现在让我们使用 sorted() 方法对元组进行排序：
sorted(mytuple)
使用字典
在 Python 字典中，数据以键和值的形式存储。
我们将使用键作为元素的优先级编号，使用值作为队列元素的值。
这样，我们就可以使用默认的 Python 字典来实现 Priority Queue。
创建字典并添加项目（键和值）：
mydict = {2: "Asia", 4: "Europe", 3: "America", 1: "Africa"}
创建字典后，我们需要按键对其项目进行排序。
我们需要使用字典 items() 方法将字典的项目存储到一个变量中：
dict_items = mydict.items()
现在使用 sorted() 函数并打印排列好的优先队列：
print(sorted(dict_items))
要从字典优先级队列中弹出项目，我们可以使用 popitem() 方法。
字典 popitem() 方法将使具有最高优先级的元素出列：
mydict = {2: "Asia", 4: "Europe", 3: "America", 1: "Africa"}
mydict.popitem()
print(mydict)
使用队列模块
让我们使用 Python 中的内置队列模块创建一个优先级队列。
使用 queue 模块是 Priority Queue 最简单的用法。
代码：
import queue p_queue = queue.PriorityQueue() p_queue.put((2, "A")) p_queue.put((1, "B")) p_queue.put((3, "C"))
在这段代码中，构造函数 PriorityQueue() 创建了一个优先队列并将其存储在变量 p_queue 中。
PriorityQueue 类的 put(priority_number, data) 函数在队列中插入一个项目。
put(priority_number, data) 函数有两个参数：第一个参数是一个整数，用于指定队列中元素的优先级编号，第二个参数是要插入队列的元素。
要从队列中弹出和返回项目，使用 get() 函数：
print(p_queue.get())
如我们所见，所有项目都已出列。
要检查队列中是否存在任何元素，请使用 empty() 函数。
empty() 函数返回一个布尔值。
如果返回 true，则表示队列为空。
p_queue.empty()
使用 heapdict
heapdict 模块类似于 Python 中的常规字典，但在 heapdict 中，我们可以弹出项目，也可以更改优先队列中项目的优先级。
使用 heapdict，我们可以更改项目的优先级：即增加或者减少项目的键。
默认情况下未安装 heapdict 模块。
安装 heapdict：
pip install heapdict
现在让我们实现优先队列：
代码：
import heapdict hd = heapdict.heapdict() hd['pen'] = 3 hd['notebook'] = 1 hd['bagpack'] = 4 hd['lunchbox'] = 2 while hd: print(hd.popitem())
使用 heapq
计算机世界中的堆数据结构主要是为了实现优先级队列。
Python 中的 heapq 模块可用于实现优先级队列。
代码：
import heapq employees = [] heapq.heappush(employees, (3, "Andrew")) heapq.heappush(employees, (1, "John")) heapq.heappush(employees, (4, "Jean")) heapq.heappush(employees, (2, "Eric")) while employees: print(heapq.heappop(employees))
在这段代码中，创建了一个堆，并将元素（优先键、值）推入堆中。
heapq 模块默认实现 min-heap。
具有最小键的元素被认为在最小堆中具有最高优先级。
因此，无论元素排队的顺序如何，最小的元素都将首先弹出，如上面的输出屏幕所示。
每当一个元素被推送或者弹出时，heapq 模块都会维护堆结构本身。
本教程将使用优先队列的 heapq 实现。
在索引处获取值
我们可以使用 Priority Queue 的堆实现来获取索引处的值。
首先创建一个堆，然后将项目推入堆中。
优先队列中的一个项目将有一个键和一个值。
这个键不是堆的索引。
这个键量化了优先级。
索引是存储优先队列的项（键、值）的位置。
考虑下面的例子：
代码：
import heapq
employees = []
heapq.heappush(employees, (3, "Andrew"))
heapq.heappush(employees, (1, "John"))
heapq.heappush(employees, (4, "Jean"))
heapq.heappush(employees, (2, "Eric"))
print("Value at index 0: ", employees[0])
print("Value at index 3: ", employees[3])
更新优先级和值
要更新优先级队列中的优先级，请获取要更新其优先级的元素的索引，并为该元素分配一个新键。
我们也可以更改元素的值。
看看下面的代码：
代码：
import heapq hq = [] heapq.heappush(hq, (3, "Jean")) heapq.heappush(hq, (2, "Eric")) heapq.heappush(hq, (4, "Monica")) heapq.heappush(hq, (1, "oiry")) print(hq) hq[1] = (6, 'Eric') print(hq) heapq.heapify(hq) print(hq)
更新一个元素的优先级后，我们需要对堆进行堆化以维护堆数据结构。
heapq 模块的 heapify() 方法将 Python 可迭代对象转换为堆数据结构。
队列是一种以称为 FIFO（先进先出）的顺序检索数据项的数据结构。
在 FIFO 中，第一个插入的元素将首先从队列中弹出。
优先队列是队列数据结构的高级版本。
具有最高优先级的元素位于优先级队列的最顶部，并且是第一个出队的元素。
有时，队列包含具有相同优先级的项目；因此，项目将根据它们在队列中的顺序出队，就像在 FIFO 中一样。
在 Python 中，有几个选项可以实现优先队列。
Python 中的队列标准库支持优先队列。
同样，Python 中的 heapq 模块也实现了 Priority Queue。
我们还可以使用 list 、 dict 和 tuple 模块来实现优先级队列。
在本教程中，我们将学习如何创建优先队列以及可以对优先队列中的元素执行的各种其他操作。
重复键（同等优先级）
如果 Priority Queue 中元素的 key 有重复，则表示这些元素的优先级相同。
但问题是哪个元素将首先出列？
那么，位于队列顶部的元素将首先从队列中出队。
代码：
import heapq heap = [] heapq.heappush(heap, (3, "Africa")) heapq.heappush(heap, (2, "America")) heapq.heappush(heap, (1, "Asia")) heapq.heappush(heap, (1, "Europe")) while heap: print(heap.pop())
查找顶部的项而不删除
为了在不弹出队列的情况下找到顶部的项目，heapq 提供了一个名为 nlargest(n, heap) 的函数。
此函数返回优先级队列中的 n 个顶部项目。
代码：
import heapq heap = [] heapq.heappush(heap, (3, "eat")) heapq.heappush(heap, (1, "study")) heapq.heappush(heap, (2, "rest")) heapq.heappush(heap, (4, "sleep")) heapq.nlargest(3, heap) print(heap)
在输出中可以看到，当使用 nlargest() 函数时，优先级队列顶部的项目被返回。
请注意，该函数仅返回项目，并且不会如打印命令所示将项目出列。
查找底部的项而不删除
为了在不弹出优先级队列的底部查找项目，heapq 提供了一个名为 nsmallest(n, heap) 的函数。
此函数返回优先级队列底部的 n 个项目。
代码：
import heapq heap = [] heapq.heappush(heap, (3, "eat")) heapq.heappush(heap, (1, "study")) heapq.heappush(heap, (2, "rest")) heapq.heappush(heap, (4, "sleep")) heapq.nsmallest(3, heap) print(heap)
在输出中可以看到，当使用 nsmallest() 函数时，优先级队列底部的项目被返回。
请注意，该函数仅返回项目，并且不会如打印命令所示将项目出列。
替换元素
在 Priority Queue 的堆实现中，我们可以弹出具有最高优先级的项目并同时推送新项目，这意味着我们正在用新项目替换最高优先级项目。
这是在名为 heapreplace 的 heapq 函数的帮助下完成的：
heapq.heapreplace(heap, item)
我们将传递队列以从中弹出项目并传递新项目以添加到队列中。
代码：
import heapq hq = [] heapq.heappush(hq, (3, "Jean")) heapq.heappush(hq, (2, "Eric")) heapq.heappush(hq, (4, "Monica")) heapq.heappush(hq, (1, "oiry")) heapq.heapify(hq) print(hq) heapq.heapreplace(hq, (6, "Ross")) print(hq)
heapreplace() 函数将具有最高优先级的元素从队列中取出，并将新元素添加到队列中。
新元素的优先级最低。
因此，它被放在队列的最后。
heapq 模块还提供了一个名为 heappushpop(heap, item) 的方法。
heappushpop(heap, item) 结合了 heappop() 和 heappush() 方法的功能。
heappushpop() 方法提高了效率，并且比使用单独的函数推送和弹出元素花费的时间更少。
heapreplace() 和 heappushpop() 的区别在于 heapreplace() 先弹出 item，然后将 item 推入队列，这是替换元素的实际定义。
而 heappushpop() 将一个项目推入队列，改变队列的大小，然后弹出最小（最高优先级）元素。
代码：
import heapq heap = [] heapq.heappush(heap, (3, "Africa")) heapq.heappush(heap, (2, "America")) heapq.heappush(heap, (1, "Asia")) heapq.heappush(heap, (4, "Europe")) heapq.heappushpop(heap, (5, "Antarctica")) while heap: heapq.heappop(heap)
为什么是优先队列？
优先队列在计算机世界中有很多应用。
例如：
- 操作系统使用优先级队列在不同的计算单元之间平衡或者分配负载（任务集）。这使得处理高效，因此引入了并行计算。
- 优先队列用于操作系统中的中断处理。
- 在人工智能中，Priority Queue 实现了 A* 搜索算法。它跟踪未探索的路线并找到图的不同顶点之间的最短路径。路径的长度越小，其优先级就越高。
- 在实现 Dijkstra 算法时，Priority Queue 可以有效地找到矩阵或者邻接表图中的最短路径。
- 优先队列对堆进行排序。堆是优先队列的一个实现。
优先队列与最小堆
优先级队列是堆的实现。
因此，此实现可以是最大堆或者最小堆。
如果优先队列的实现是最大堆，那么它将是一个最大优先级队列。
同样，如果实现是最小堆，那么优先级队列将是一个最小优先级队列。
在最小堆中，最小的节点是二叉树的根。
优先级队列和最小堆是相同的。
唯一的区别是在优先级队列中元素的顺序取决于元素的优先级编号。