知识卡片

结构图卡 · 5666.b

优先队列显式编码比较规则

理解等级:中级

需要每次弹出最高优先级元素时,可用最小堆保存(-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排版缩进有误,方法归属据调用与说明理解,不声称原样可运行。

这张卡片看不懂?

已有反馈 · 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的作用是为了将具有相同优先级的元素以适当的顺序