详解Python 优先队列

Python 优先队列使用方法的完整攻略

什么是优先队列？

优先队列是一种队列，但是每次取出的元素都是队列中优先级最高的元素，而不是按照先进先出的规则取出。优先队列可以使用堆来实现，堆是一种二叉树类型的数据结构，可以方便地排序。Python中的heapq模块提供了优先队列的相关操作。

Python中如何使用优先队列

创建优先队列

使用Python中的heapq模块，我们可以轻松创建一个优先队列。

import heapq

pq = []  #创建一个空的优先队列
heapq.heappush(pq,1) #将1加入优先队列
heapq.heappush(pq,2) #将2加入优先队列
heapq.heappush(pq,3) #将3加入优先队列

取出元素

通过Python中的heapq模块，我们可以轻松地取出优先队列中优先级最高的元素。

import heapq

pq = []
heapq.heappush(pq,1)
heapq.heappush(pq,2)
heapq.heappush(pq,3)

print(heapq.heappop(pq)) # 取出队列中优先级最高的元素，并从队列中删除

上面代码输出结果为：

1

更改元素优先级

我们可以使用一个类来存储元素和元素的优先级，然后使用heapq模块中的heapreplace函数来更改元素的优先级。

import heapq

class Element:
  def __init__(self, priority, value):
    self.priority = priority
    self.value = value

  # __lt__方法是只有一个元素可以比较大小时所调用的方法
  def __lt__(self, other):
    return self.priority < other.priority

pq = []
heapq.heappush(pq, Element(3, 'A'))
heapq.heappush(pq, Element(2, 'B'))
heapq.heappush(pq, Element(1, 'C'))

pq[2].priority = 3
heapq.heapify(pq)

while len(pq) > 0:
  print(heapq.heappop(pq).value)

上面代码输出结果为：

B
A
C

其他相关函数

heapq模块还提供了一些其他有用的函数，例如heapreplace函数可以将队列中的元素更改为新元素。heappushpop函数与heapreplace函数非常相似，但是在将新元素放入队列之前会取出队列中优先级最高的元素，因此具有更快的速度。

import heapq

pq = []
heapq.heappush(pq,1)
heapq.heappush(pq,2)
heapq.heappush(pq,3)

print(pq) #[1, 2, 3]

heapq.heapreplace(pq, 4)
print(pq) #[2, 4, 3]

heapq.heappushpop(pq, 5)
print(pq) #[3, 4, 5]

上面代码输出结果为：

[1, 2, 3]
[2, 4, 3]
[3, 4, 5]