知识卡片

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

堆提取插入各走一条路径

理解等级:中级

最大堆提取最大值时取根、以末元素补根、缩小堆并向下堆化。

插入时在末尾扩一叶,以 −∞ 初始化,再增键向上浮动。

两者只沿一条根叶路径修复,故操作时间 O(log n),另加对象索引映射成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 6 章 6.5 节、Problems 与 Chapter notes(`OEBPS/chapter006.xhtml`,文本字符 [25000, 30000);图 6.5)。 - 结论依据:6.5 节提取最大值以末元素补根并调用堆化,插入则在末尾加元素再调用增键;各只沿一条树路径,且对象索引映射另计。 - 原始内容:The running time of M AX -H EAP -I NSERT on an n -element heap is O (lg n ) plus the overhead for mapping priority queue objects to indices.