知识卡片
单调提取可用专门队列
若连续 EXTRACT-MIN 返回的键值随时间单调不减,就是单调优先队列场景。
书中以 Dijkstra 和离散事件模拟为例;在受限整数键范围下,可使用基数堆等专用结构改善某些操作界。
应用前需证明这一单调前提。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.