知识卡片
建堆从末个内部节点逆行
BUILD-MAX-HEAP 从 ⌊n/2⌋ 到 1 逆序调用 MAX-HEAPIFY。更大索引的叶子天然成堆,处理某节点时两子树已成堆,正好满足堆化前提;正序处理则无法维持这个不变量。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第6章 堆排序 · 查看原书依据
BUILD-MAX-HEAP converts an array A[1 : n] into a max-heap by calling MAX-HEAPIFY in a bottom-up manner.
参考来源
- 位置:《算法导论(第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.