Python 优先级队列 PriorityQueue 简单使用方法

Python 优先级队列是比较好用的数据结构，使用具有全序关系的键（例如用数值表示的权重）来管理元素，以便快速访问容器中键值最小或最大的元素。优先队列可被视为队列的改进版，其中元素的顺序不是基于插入时间，而是基于优先级的。对键进行处理能得到每个元素的优先级。优先级队列通常用于处理调度问题，例如优先考虑更加紧急的任务。

目前 Python 有多种优先级队列的实现方法，本文仅介绍最推荐的一种方法，更多方法参考原文：《Python 优先队列》。

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')

关键要点：

• Python提供了几种优先队列实现可以使用。
• queue.PriorityQueue是其中的首选，具有良好的面向对象的接口，从名称就能明白其用途。
• 如果想避免queue.PriorityQueue的锁开销，那么建议直接使用heapq模块。