知识卡片

普通读书笔记卡 · 3613.a

堆序性质区分大小堆

理解等级:中级

最大堆要求每个非根节点的键不大于父节点,因此根是全堆最大值;

最小堆反向,根是最小值。

堆序只约束祖先与后代,不要求兄弟或任意两节点有序;堆排序用最大堆,优先队列按取极值方向选堆。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 ]