知识卡片

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

堆化须已有子堆前提

理解等级:中级

MAX-HEAPIFY 假设左右子树已分别是最大堆,仅根 i 可能过小。

把 i 与两孩子中的最大值交换,再沿被换下的子树递归,直到堆序恢复。

每层常数比较与交换,最多下降树高,故耗时 O(log n);没有子堆前提则不能保证修复整个树。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 6 章(`OEBPS/chapter006.xhtml`,文本字符 [5000, 10000);图 6.1–6.4 与公式图 Art_P298–P304)。 - 结论依据:6.2 节给 MAX-HEAPIFY 的明确前提:左右子树已是最大堆,只有 A[i] 可能小于孩子;算法把过小的根沿一路下沉。 - 原始内容:When it is called, M AX -H EAPIFY assumes that the binary trees rooted at L EFT ( i ) and R IGHT ( i ) are max-heaps