如何使用 Python 堆实现优先队列？

2023-04-11 00:00:00 队列 如何使用 优先

Python 中的 heapq 模块提供了堆的实现。堆是一个可以自动调整的数据结构，可以用来实现优先队列。优先队列由两部分组成：一是待优化的数列，二是各个数在队列中的优先级。优先级最高的数先出队列。

下面我们来看一下如何使用 Python 堆实现优先队列：

  1. 导入 heapq 模块
import heapq
  1. 创建空的堆列表
heap = []
  1. 向堆中添加元素
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
  1. 从堆中取出元素
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2
  1. 查看堆的元素
print(heap)  # [5, 10]
  1. 自定义堆的排序规则

如果要自定义堆的排序规则，可以将元素作为元组 (priority, value) 添加到堆中。priority 表示元素的优先级，value 表示元素的值。

例如，下面的代码将元素按照 value 的长度作为优先级排序：

heap = []
heapq.heappush(heap, (len('pidancode.com'), 'pidancode.com'))
heapq.heappush(heap, (len('皮蛋编程'), '皮蛋编程'))

print(heapq.heappop(heap)[1])  # 皮蛋编程
print(heapq.heappop(heap)[1])  # pidancode.com

完整代码如下：

import heapq

# 创建空的堆列表
heap = []

# 向堆中添加元素
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)

# 从堆中取出元素
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2

# 查看堆的元素
print(heap)  # [5, 10]

# 自定义堆的排序规则
heap = []
heapq.heappush(heap, (len('pidancode.com'), 'pidancode.com'))
heapq.heappush(heap, (len('皮蛋编程'), '皮蛋编程'))
print(heapq.heappop(heap)[1])  # 皮蛋编程
print(heapq.heappop(heap)[1])  # pidancode.com

相关文章