知识卡片
堆化须已有子堆前提
MAX-HEAPIFY 假设左右子树已分别是最大堆,仅根 i 可能过小。
把 i 与两孩子中的最大值交换,再沿被换下的子树递归,直到堆序恢复。
每层常数比较与交换,最多下降树高,故耗时 O(log n);没有子堆前提则不能保证修复整个树。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第6章 堆排序 · 查看原书依据
When it is called, MAX-HEAPIFY assumes that the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps
参考来源
- 位置:《算法导论(第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