知识卡片

普通读书笔记卡 · 5654.d.1.e.2.a.3.a

自下而上建堆是线性工作

理解等级:中级

把所有值先放入数组,再从最后一个非叶节点向前逐个下沉。处理某节点时,其孩子子树已经是合法堆,因此一次向下修复就能建立更大的合法子堆。

靠近叶子的节点很多但可下降距离很短,靠近根的节点少但路径长,按高度加权总工作为线性。把每个节点都按最高对数路径相乘会高估;逐个上浮插入的建堆则通常为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