python标准库无动态更新优先队列，需用heapq+dict实现惰性删除：push时标记旧条目、入新条目，pop时跳过失效项，确保o(log n)均摊复杂度。
Python标准库没有支持动态更新的优先队列
Python的heapq模块只提供最小堆的原地操作，不支持按元素查找或删除任意节点。当你需要“根据某个ID更新其优先级”（比如Dijkstra中松弛边后要降低某节点的距离），直接调用heapq.heappush()会留下旧条目，而heapq.heapremove()根本不存在——这是最常踩的坑。
常见错误现象：KeyError 或重复处理同一节点，导致算法结果错误或死循环。
- 不要试图用
list.remove()再heapify()：时间复杂度退化到O(n)，破坏堆的效率优势 - 避免维护两个同步结构（如堆+字典）却不标记过期项：旧权重仍可能被
heappop()取出 - 真正可行的路径是“惰性删除”+“字典索引”：用字典记录每个ID当前最优权重，入堆时带版本号或直接接受冗余
用heapq + dict实现带惰性删除的优先队列
核心思路：每次更新权重时，不删旧条目，而是把新条目推入堆；出队时跳过已失效的条目。字典entry_finder存ID→最新权重，堆里每个元素是(priority, count, item)三元组，其中count确保插入顺序可比（避免priority相同时比较不可哈希的item）。
import heapq
<p>class PriorityQueue:
def <strong>init</strong>(self):
self._heap = []
self._entry_finder = {}
self._counter = 0 # 用于打破优先级相同时的平局</p><pre class="brush:python;toolbar:false;">def push(self, item, priority):
if item in self._entry_finder:
self._remove_item(item)
count = self._counter
self._counter += 1
entry = [priority, count, item]
self._entry_finder[item] = entry
heapq.heappush(self._heap, entry)
def _remove_item(self, item):
entry = self._entry_finder.pop(item)
entry[-1] = None # 标记为已删除
def pop(self):
while self._heap:
priority, count, item = heapq.heappop(self._heap)
if item is not None:
del self._entry_finder[item]
return item, priority
raise KeyError('pop from empty priority queue')
使用场景：Dijkstra、A*、任务调度器中需反复调整任务优先级。注意push()内部调用_remove_item()只是标记，不触发堆重排，所以均摊时间仍是O(log n)。
为什么不用queue.PriorityQueue
queue.PriorityQueue是线程安全封装，底层仍用heapq，但不暴露内部堆结构，无法做惰性删除或字典索引。它没有update()、contains()等方法，也无法访问或修改已有条目——强行用它做动态更新，只能清空重建，完全失去增量更新的意义。
- 如果你的应用不需要并发，别用
queue.PriorityQueue：多一层封装无益，反而锁开销和接口限制更麻烦 - 如果真要线程安全，应在
PriorityQueue类外加threading.Lock，而不是依赖其内置锁（它锁的是整个队列，不是单个操作） - 它的
put()和get()不返回优先级值，你无法知道取出来的是哪个权重，对调试和验证不利
实际使用时容易忽略的边界点
动态权重更新最关键的不是怎么写，而是怎么用：很多人实现了类，却在业务逻辑里忘了检查是否已存在、或误把pop()返回的item当权重用。
- 调用
push()前必须确认item可哈希且唯一（比如用(node_id, task_type)元组，别用含列表的结构） -
pop()返回的是(item, priority)，不是仅item；漏读priority会导致后续比较逻辑出错 - 堆中残留的“已删除”条目不会自动清理，长期运行后内存缓慢增长——若ID空间有限（如固定1000个节点），影响不大；若是流式ID（如请求ID），建议定期
self._heap = [e for e in self._heap if e[2] is not None]并heapify()，但仅在检测到堆积严重时才做
真正的难点永远在状态一致性：字典里的权重、堆里的条目、业务代码里的变量，三者必须严格同步。哪怕一次忘记push()前检查in，就可能让旧权重重新生效。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
