知识卡片
堆元素迁移须维护句柄
把应用对象放入数组堆时,增键或删除需先找到对象当前索引。
可在对象与堆元素间维护句柄,或由优先队列保存对象到索引的映射;每次交换都必须同步更新映射。
否则键调整可能改错位置,复杂度也要计入映射成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第6章 堆排序 · 查看原书依据
Because heap elements change locations within the array during heap operations, an actual implementation of the priority queue, upon relocating a heap element, must also update the array indices in the corresponding handles.
参考来源
- 位置:《算法导论(第4版)》第 6 章 6.5 节、Problems 与 Chapter notes(`OEBPS/chapter006.xhtml`,文本字符 [20000, 25000);图 6.5)。
- 结论依据:6.5 节指出堆元素在数组内迁移时,对应应用对象的 handle 所存索引必须随交换更新,否则无法定位其新位置。
- 原始内容:Because heap elements change locations within the array during heap operations, an actual implementation of the priority queue, upon relocating a heap element, must also update the array indices in the corresponding handles.