Python 优先队列|极客教程

Python 优先队列，优先队列是一个容器数据结构，使用具有全序关系的键（例如用数值表示的权重）来管理元素，以便快速访问容器中键值最小或最大的元素。

优先队列可被视为队列的改进版，其中元素的顺序不是基于插入时间，而是基于优先级的。对键进行处理能得到每个元素的优先级。

优先级队列通常用于处理调度问题，例如优先考虑更加紧急的任务。

来看看操作系统任务调度器的工作。

理想情况下，系统上的高优先级任务（如玩实时游戏）级别应高于低优先级的任务（如在后台下载更新）。优先级队列将待执行的任务根据紧急程度排列，任务调度程序能够快速选取并优先执行优先级最高的任务。

本节将介绍如何使用Python语言内置或位于标准库中的数据结构来实现优先队列。每种实现都有各自的优缺点，但其中有一种实现能应对大多数常见情况，下面一起来看看。

Python 优先队列列表——手动维护有序队列

使用有序列表能够快速识别并删除最小或最大的元素，缺点是向列表插入元素表是很慢的操作。
虽然用标准库中的bisect.insort能在时间内找到插入位置，但缓慢的插入操作才是瓶颈。

向列表添加并重新排序来维持顺序也至少需要的时间。另一个缺点是在插入新元素时，必须手动重新排列列表。缺少这一步就很容易引入bug，因此担子总是压在开发人员身上。

因此，有序列表只适合在插入次数很少的情况下充当优先队列。

q = []

q.append((2, 'code'))
q.append((1, 'eat'))
q.append((3, 'sleep'))

# 注意：每当添加新元素或调用bisect.insort()时，都要重新排序。
q.sort(reverse=True)

while q:
    next_item = q.pop()
    print(next_item)

# 结果：
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

Python 优先队列 `heapq`——基于列表的二叉堆

heapq是二叉堆，通常用普通列表实现，能在时间内插入和获取最小的元素。

heapq模块是在Python中不错的优先级队列实现。由于heapq在技术上只提供最小堆实现，因此必须添加额外步骤来确保排序稳定性，以此来获得“实际”的优先级队列中所含有的预期特性。

import heapq

q = []

heapq.heappush(q, (2, 'code'))
heapq.heappush(q, (1, 'eat'))
heapq.heappush(q, (3, 'sleep'))

while q:
    next_item = heapq.heappop(q)
    print(next_item)

# 结果：
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

Python 优先队列 `queue.PriorityQueue`——美丽的优先级队列

queue.PriorityQueue这个优先级队列的实现在内部使用了heapq，时间和空间复杂度与heapq相同。

区别在于PriorityQueue是同步的，提供了锁语义来支持多个并发的生产者和消费者。

在不同情况下，锁语义可能会带来帮助，也可能会导致不必要的开销。不管哪种情况，你都可能更喜欢PriorityQueue提供的基于类的接口，而不是使用heapq提供的基于函数的接口。

from queue import PriorityQueue

q = PriorityQueue()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

while not q.empty():
    next_item = q.get()
    print(next_item)

# 结果：
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

关键要点