Python中heapq模块 堆队列算法heapq的优先级队列实现

在python中，使用heapq模块可以很方便地实现优先级队列。堆（heap）是一种特殊的树结构，常用于快速获取最小值或最大值的场景。heapq默认实现的是最小堆，也就是说堆顶元素始终是整个堆中最小的那个。

什么是优先级队列？

优先级队列是一种数据结构，每个元素都带有一个“优先级”。当访问或删除元素时，优先级更高的元素会优先被处理。比如任务调度、医院挂号系统等场景都会用到这种结构。

常见的做法是将每个元素和它的优先级打包成一个元组，然后插入堆中。Python的heapq会根据元组的第一个元素进行排序，从而实现优先级控制。

如何用heapq创建优先级队列

使用heapq实现优先级队列非常简单，只需要导入模块并维护一个堆列表即可：

• 使用heapq.heappush()添加元素
• 使用heapq.heappop()弹出当前优先级最高的元素（即最小的）

例如：

立即学习“Python免费学习笔记（深入）”；

import heapq

queue = []
heapq.heappush(queue, (3, '写报告'))
heapq.heappush(queue, (1, '回邮件'))
heapq.heappush(queue, (2, '开会'))

print(heapq.heappop(queue))  # 输出：(1, '回邮件')

每次调用heappop()都会取出当前优先级最高的任务。

注意：如果两个元素的优先级相同（比如都是2），那么它们之间的顺序取决于后面的元素内容，在heapq中不保证稳定排序。

处理优先级相同的情况

当多个任务拥有相同的优先级时，你可能还希望这些任务能按照它们插入的顺序来处理。这时候可以在元组中加入第三个字段，比如时间戳：

import heapq
import time

queue = []
timestamp = 0

def add_task(priority, task):
    global timestamp
    heapq.heappush(queue, (priority, timestamp, task))
    timestamp += time.time()

add_task(2, '任务A')
add_task(2, '任务B')
add_task(1, '紧急任务')

print(heapq.heappop(queue))  # 紧急任务先出
print(heapq.heappop(queue))  # A比B早添加，所以先出
print(heapq.heappop(queue))  # 最后才是B

这样即使优先级相同，也能通过时间戳保持插入顺序。

常见问题与注意事项

• heapq默认是最小堆，如果你需要最大堆行为，可以把优先级取负数再插入。

  heapq.heappush(queue, (-priority, task))

  登录后复制

• 不要直接操作堆列表，比如用append()而不是heappush()，这会导致堆结构损坏。

• heapq适用于中小型数据量。如果数据特别大或者频繁操作，要考虑其他结构如线段树、平衡树等。

基本上就这些。heapq虽然简单，但配合元组使用就能轻松实现优先级队列功能，适合很多实际场景。只要注意好插入和弹出的方式，以及优先级冲突的处理方式，基本不会出错。

以上就是Python中heapq模块 堆队列算法heapq的优先级队列实现的详细内容，更多请关注php中文网其它相关文章！