Python优先队列实现详解

Python的优先队列并非由某个现成的“PriorityQueue类”直接提供，而是以轻量、高效、灵活的heapq模块为核心——它不封装对象，而是原地维护列表的最小堆结构，通过heappush/heappop实现O(log n)级插入与弹出；需最大堆时只需巧妙取反或元组包装，切忌依赖私有API；单线程场景下直接使用heapq远胜于过度包装的queue.PriorityQueue，后者仅在多线程生产者-消费者模型中才真正发挥价值；而要让自定义对象入堆，唯一可靠的方式是正确定义__lt__方法——理解这些底层逻辑，才能避开排序误解、性能陷阱和线程误用，写出既正确又高效的优先级调度代码。

Python 里 heapq 就是优先队列的底层实现

Python 标准库没有叫 PriorityQueue 的类来直接当“队列”用，但 heapq 模块提供了一组原地操作最小堆的函数，这才是实际干活的核心。你不是在“创建一个队列对象”，而是在维护一个列表，靠 heapq.heappush() 和 heapq.heappop() 保证它始终满足堆序。

常见错误是以为 heapq 自动排序整个列表——其实它只维护堆结构，不保证列表其余部分有序；还有人误用 sorted() 替代 heappop()，结果每次取最小值都 O(n log n)，而不是 O(log n)。

• heapq.heappush(heap, item)：把 item 插入 heap 并调整结构，时间复杂度 O(log n)
• heapq.heappop(heap)：弹出并返回最小元素，同时修复堆，O(log n)
• 初始化堆用 heapq.heapify(lst)，比逐个 heappush 快，O(n)
• 不要手动修改 heap 列表（比如 heap[0] = x），会破坏堆性质

需要最大堆？别改源码，改数据就行

Python 的 heapq 只支持最小堆，但多数场景要的是“最大优先级先出”。最稳妥的做法不是重写堆逻辑，而是对数值取反或包装成元组，让比较逻辑倒过来。

比如你要按分数降序取学生：heapq 默认按第一个元素升序，所以把 (-score, student_id) 入堆，heappop 后再取负号还原即可。字符串或自定义对象也类似，关键在于让 __lt__ 行为符合你的“优先级高低”定义。

• 数值型：存 -x，取出来再 -item
• 多字段：用元组 (-priority, timestamp, item)，确保可比且稳定
• 避免用 max heap = heapq._heapify_max：这是私有 API，不保证兼容，Python 3.12 已明确标记为内部使用
• 如果频繁需要最大堆，封装一层类比裸用 heapq 更安全，但别过度设计

queue.PriorityQueue 是线程安全的包装，别在单线程里滥用

标准库里的 queue.PriorityQueue 确实名字像“正统优先队列”，但它本质是用 heapq 加了锁的封装，目标是多线程生产者-消费者场景。如果你在单线程脚本、算法题或数据处理中用它，反而引入不必要的开销和 API 隔离（比如不能直接访问底层列表）。

典型误用：用 PriorityQueue.put(x) 和 PriorityQueue.get() 写 Dijkstra，结果发现没法做“减小键值”（decrease-key）操作，也没法检查某个节点是否已在队列中——因为它的接口不暴露内部状态。

• 单线程、需灵活控制（如更新权重、查存在性）→ 直接用 heapq + 搭配字典或集合
• 多线程、只需“塞进去、取出来”且不关心中间状态 → queue.PriorityQueue 合理
• queue.PriorityQueue 不支持 len() 以外的长度外查，也不支持索引访问
• 它的 put() 和 get() 是阻塞式，默认会等锁，哪怕队列非空

自定义比较逻辑时，__lt__ 是唯一靠谱入口

想让类实例能进 heapq，必须定义 __lt__（less-than）。Python 堆操作只调这个方法做比较，其他如 __eq__ 或 __gt__ 完全无关。很多人试了 __cmp__（Python 2）或试图重载 >，结果报 TypeError: '。

注意：如果两个对象 __lt__ 返回 False，不代表它们相等，可能只是“不小于”，堆操作仍可能出错。稳妥做法是让 __lt__ 总返回布尔值，并确保逻辑可传递、无歧义。

• 只实现 __lt__，别碰 __le__ 或 __gt__，heapq 不用它们
• 元组天然可比，所以 (priority, insertion_count, obj) 是避免自定义类的好技巧
• 如果 priority 相同，不加 insertion_count 可能导致不可预测的顺序（取决于对象 id 比较，而它不保证稳定）
• 别在 __lt__ 里做耗时计算或 I/O，堆操作本身高频，慢逻辑会拖垮性能

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Python优先队列实现详解》文章吧，也可关注golang学习网公众号了解相关技术文章。