知识卡片

普通读书笔记卡 · 3613.a.2.d

单调提取可用专门队列

理解等级:中级

若连续 EXTRACT-MIN 返回的键值随时间单调不减,就是单调优先队列场景。

书中以 Dijkstra 和离散事件模拟为例;在受限整数键范围下,可使用基数堆等专用结构改善某些操作界。

应用前需证明这一单调前提。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第6章 堆排序 · 查看原书依据

      An important special case of priority queues occurs when the sequence of EXTRACT-MIN operations is monotone, that is, the values returned by successive EXTRACT-MIN operations are monotonically increasing over time.

    参考来源

    - 位置:《算法导论(第4版)》第 6 章 6.5 节、Problems 与 Chapter notes(`OEBPS/chapter006.xhtml`,文本字符 [30000, 35000);图 6.5)。 - 结论依据:第6章注释把连续 EXTRACT-MIN 返回值单调递增界定为特例,并举 Dijkstra 等用途;专用整数键队列的改进有额外键域前提。 - 原始内容:An important special case of priority queues occurs when the sequence of E XTRACT -M IN operations is monotone , that is, the values returned by successive E XTRACT -M IN operations are monotonically increasing over time.