知识卡片

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

堆元素迁移须维护句柄

理解等级:中级

把应用对象放入数组堆时,增键或删除需先找到对象当前索引。

可在对象与堆元素间维护句柄,或由优先队列保存对象到索引的映射;每次交换都必须同步更新映射。

否则键调整可能改错位置,复杂度也要计入映射成本。

这张卡片看不懂?

已有反馈 · 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.