知识卡片

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

入堆从末位向上修复

理解等级:中级

新元素先放在数组末尾,维持完全树形状;如果优先级高于父节点,就交换并继续向上,直到父子关系合法或已到根。其他子树原本合法,只需修复这一条路径。

路径长度为对数,但底层追加若触发扩容,单次存储成本还可能线性,通常需给均摊前提。根没有父节点,Go整数除法对负数趋零,不能把(i-1)/2对i==0的结果直接当数学向下整除。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      从底至顶修复堆中的各个节点,直至越过根节点或遇到无须 交换的节点时结束。 第8 章 堆 hello‑algo.com 178 图8‑3 元素入堆步骤 设节点总数为 ,则树的高度为 log 。由此可知,堆化操作的循环轮数最

    参考来源

    - 位置:《Hello 算法--Go版本》第08章《堆》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[18718,18828)) - 结论依据:实际push/siftUp路径代码与完全树高度支持,补充Go除法根界。 - 原始内容:从底至顶修复堆中的各个节点,直至越过根节点或遇到无须 交换的节点时结束。 第8 章 堆 hello‑algo.com 178 图8‑3 元素入堆步骤 设节点总数为 ,则树的高度为 log 。由此可知,堆化操作的循环轮数最