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模块。

【AD】美国洛杉矶CN2 VPS/香港CN2 VPS/日本CN2 VPS推荐,延迟低、稳定性高、免费备份_搬瓦工vps

【AD】RackNerd 推出的 KVM VPS 特价优惠,在纽约、西雅图、圣何塞和阿什本每年仅需 12.88 美元!