Python 标准库 —— queue heapq与PriorityQueue

优先队列，有别于普通队列的先入先出（虽然字面上还是队列，但其实无论从含义还是实现上，和普通队列都有很大的区别），也有别于栈的先入后出。在实现上，它一般通过堆这一数据结构，而堆其实是一种完全二叉树，它会对进入容器的元素进行排序（根据事先指定的规则），出队的顺序则会是二叉树的根结点代表的元素。

1. queue 与 queue.PriorityQueue

import queueclass ComparableObj: # 可比较对象，放入优先队列中def __init__(self, **):...def __cmp__(self, other): # 比较规则的指定，谁做根（大顶堆，小顶堆）# 返回的是布尔类型...return True/Flase...que = Queue.PriorityQueue()que.put(ComparableObj(**))que.put(ComparableObj(**))...que.qsize()# 优先队列中元素的个数que.get()# 返回根（优先队列第一个出队的元素）

2. heapq：将list转换为等价的优先队列

import heapq li = [5, 7, 9, 1, 3] heapq.heapify(li) # [1, 3, 9, 7, 5]heapq.heappush(li,4) # [1, 3, 4, 7, 5, 9]heapq.heappop(li)# 1# li ⇒ [3, 5, 4, 7, 9]

references

Python 的优先队列示例Heap queue (or heapq) in Python

如果觉得《Python 标准库 —— queue heapq与PriorityQueue》对你有帮助，请点赞、收藏，并留下你的观点哦！