知识卡片
入堆从末位向上修复
新元素先放在数组末尾,维持完全树形状;如果优先级高于父节点,就交换并继续向上,直到父子关系合法或已到根。其他子树原本合法,只需修复这一条路径。
路径长度为对数,但底层追加若触发扩容,单次存储成本还可能线性,通常需给均摊前提。根没有父节点,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 。由此可知,堆化操作的循环轮数最