知识卡片

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

出堆用末项接替后向下修复

理解等级:中级

先交换根与最末项,再删去末尾的原堆顶,让最后一个值接替根。比较它与孩子,选优先级最高的孩子交换并继续,直到无需交换或到叶子。

这同时保持完全形状并修复唯一可能破坏的向下路径,避免删除首元素造成所有索引整体移动。空堆必须先处理,且只在有效堆长度内检查孩子。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      交换堆顶元素与堆底元素(交换根节点与最右叶节点) 。 2. 交换完成后,将堆底从列表中删除(注意,由于已经交换,因此实际上删除的是原来的堆顶元素) 。 3. 从根节点开始,从顶至底执行堆化 。 如图8‑4 所示,“从顶至

    参考来源

    - 位置:《Hello 算法--Go版本》第08章《堆》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[19384,19494)) - 结论依据:实际三步及siftDown比较当前/左右代码支持。 - 原始内容:交换堆顶元素与堆底元素(交换根节点与最右叶节点) 。 2. 交换完成后,将堆底从列表中删除(注意,由于已经交换,因此实际上删除的是原来的堆顶元素) 。 3. 从根节点开始,从顶至底执行堆化 。 如图8‑4 所示,“从顶至