知识卡片
优先队列显式编码比较规则
需要每次弹出最高优先级元素时,可用最小堆保存(-priority, index, item):priority取负让高优先级先出,递增index在同级时保持入队顺序,并阻止比较不可排序的item。PriorityQueue.push(item, priority)加入,pop()返回载荷;空队列与并发使用仍需额外约定,原例不含线程同步。
结构图:
classDiagram
class PriorityQueue {
+push(item, priority)
+pop()
}
class Item {
+__init__(name)
+__repr__()
}
PriorityQueue o-- "*" Item : 通过堆元组保存引用
图保留原例名称和参数,聚合不表示独占生命周期;返回类型未在签名中声明,未补造。原文push/pop排版缩进有误,方法归属据调用与说明理解,不声称原样可运行。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
队列以元组(-priority, index, item)的形式组成。把priority取负值是为了让队列能够按元素的优先级从高到低的顺序排列。这和正常的堆排列顺序相反,一般情况下堆是按从小到大的顺序排序的。 变量index的作用是为了将具有相同优先级的元素以适当的顺序
参考来源
- 位置:《Python Cookbook(第3版)中文版》1.5 实现优先级队列(spine9;extracted/Python Cookbook(第3版)中文版/_epub-src/OEBPS/Text/part0007.xhtml;u007-ch01-007)。
- 结论依据:本条问题、全部示例代码与讨论已完整读取;区分算法性质、历史实现说明与本次未执行的性能结论。
- 原始内容:队列以元组(-priority, index, item)的形式组成。把priority取负值是为了让队列能够按元素的优先级从高到低的顺序排列。这和正常的堆排列顺序相反,一般情况下堆是按从小到大的顺序排序的。 变量index的作用是为了将具有相同优先级的元素以适当的顺序