知识卡片
自下而上建堆是线性工作
把所有值先放入数组,再从最后一个非叶节点向前逐个下沉。处理某节点时,其孩子子树已经是合法堆,因此一次向下修复就能建立更大的合法子堆。
靠近叶子的节点很多但可下降距离很短,靠近根的节点少但路径长,按高度加权总工作为线性。把每个节点都按最高对数路径相乘会高估;逐个上浮插入的建堆则通常为nlogn。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
底层节点数量远多于顶层节点的性质 。 接下来我们来进行更为准确的计算。为了降低计算难度,假设给定一个节点数量为 、高度为 的“完美二 叉树” ,该假设不会影响计算结果的正确性。 图8‑5 完美二叉树的各层节点数量 如图8
参考来源
- 位置:《Hello 算法--Go版本》第08章《堆》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[21631,21741))
- 结论依据:实际两种建堆方法与按层数量×高度论证,残缺推导不照抄,图8-5已读。
- 原始内容:底层节点数量远多于顶层节点的性质 。 接下来我们来进行更为准确的计算。为了降低计算难度,假设给定一个节点数量为 、高度为 的“完美二 叉树” ,该假设不会影响计算结果的正确性。 图8‑5 完美二叉树的各层节点数量 如图8