← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3613.a.1.a

建堆从末个内部节点逆行

理解等级:中级

BUILD-MAX-HEAP 从 ⌊n/2⌋ 到 1 逆序调用 MAX-HEAPIFY。更大索引的叶子天然成堆,处理某节点时两子树已成堆,正好满足堆化前提;正序处理则无法维持这个不变量。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 6 章(`OEBPS/chapter006.xhtml`,文本字符 [10000, 15000);图 6.1–6.4 与公式图 Art_P298–P304)。 - 结论依据:6.3 节 BUILD-MAX-HEAP 伪代码由 ⌊n/2⌋ 逆行到 1;循环不变量是处理 i 时后面的每个节点已为最大堆根。 - 原始内容:B UILD -M AX -H EAP converts an array A [1 : n ] into a max-heap by calling M AX -H EAPIFY in a bottom-up manner.