知识卡片
堆序性质区分大小堆
最大堆要求每个非根节点的键不大于父节点,因此根是全堆最大值;
最小堆反向,根是最小值。
堆序只约束祖先与后代,不要求兄弟或任意两节点有序;堆排序用最大堆,优先队列按取极值方向选堆。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第6章 堆排序 · 查看原书依据
In a max-heap, the max-heap property is that for every node i other than the root, A[PARENT(i)] ≥ A[i]
参考来源
- 位置:《算法导论(第4版)》第 6 章(`OEBPS/chapter006.xhtml`,文本字符 [0, 5000);图 6.1–6.4 与公式图 Art_P298–P304)。
- 结论依据:6.1 节规定最大堆的父键不小于子键,因此根为最大;最小堆反向。该性质不约束同层或不同分支的总排序。
- 原始内容:In a max-heap , the max-heap property is that for every node i other than the root, A [P ARENT ( i )] ≥ A [ i ]