知识卡片
堆提取插入各走一条路径
最大堆提取最大值时取根、以末元素补根、缩小堆并向下堆化。
插入时在末尾扩一叶,以 −∞ 初始化,再增键向上浮动。
两者只沿一条根叶路径修复,故操作时间 O(log n),另加对象索引映射成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第6章 堆排序 · 查看原书依据
The running time of MAX-HEAP-INSERT on an n-element heap is O(lg n) plus the overhead for mapping priority queue objects to indices.
参考来源
- 位置:《算法导论(第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.