知识卡片

普通读书笔记卡 · 3613.d.2 · 生成模型:未记录

堆序只约束父子不排序兄弟

理解等级:中级

最大堆要求父节点的优先值不小于孩子,所以根含最大值;最小堆方向相反,根含最小值。相同优先值可以存在,不必把书中“比父小/大”理解为必须严格不等。

堆没有要求兄弟互相按大小排序,数组的后续位置也不是“次大、第三大”的固定顺序。02889根25,孩子20/22,局部父子关系足以保证25为最大,却不是二叉搜索树的左小右大不变量。

因此取出一个极值后要修复局部堆序,才能让下一个极值到根;直接顺数组遍历不能获得已排序结果。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      局部有序的,任何一个结点与其兄弟结点之间都没有必然的顺序关系,但它与其父子结点有大小顺序关系。子结点比父结点小的堆称为最大值堆(见图10-1),这是因为根结点存储该树所有结点的最大值。反之,子结点比父结点大的堆称为最小值堆。 图 10-1 (a)最大值堆 (b)其在数组中的表示 堆是左平衡的树(见第

    参考来源

    - 位置:《算法精解:C语言描述》第10章《堆的描述》(spine1308;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1275.html;u171-ch10-003)。 - 结论依据:171全部最大/最小/局部有序说明与02889整图实读,允许等号由实际heap比较只在严格失序时交换与MIT已读堆性质补证。 - 原始内容:局部有序的,任何一个结点与其兄弟结点之间都没有必然的顺序关系,但它与其父子结点有大小顺序关系。子结点比父结点小的堆称为最大值堆(见图10-1),这是因为根结点存储该树所有结点的最大值。反之,子结点比父结点大的堆称为最小值堆。 图 10-1 (a)最大值堆 (b)其在数组中的表示 堆是左平衡的树(见第