知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.19 · 生成模型:未记录

最大堆用数组表示完全二叉树

理解等级:中级

最大堆满足两个条件:树是完全二叉树,且每个父节点不小于其子节点。根节点因此是最大值,但兄弟之间和不同分支不必有序。零基数组中节点 i 的左右子节点是 2i+1、2i+2,非根父节点是 ⌊(i−1)/2⌋;访问前需检查索引仍在堆区间。

自底向上对非叶节点下沉可建立堆;排序时把根与堆尾交换,缩小堆区间并下沉新根。循环不变量是前缀为最大堆,后缀已升序且不小于堆中的所有元素。

87指出堆排序不稳定;频繁交换大记录可能昂贵,但这不意味着不能对值类型排序。可按应用权衡直接移动值、交换指针或排序索引,并注意间接访问和额外存储成本。

88指出堆排序避开普通快排的二次最坏情形,但两者平均性能依环境而异。堆排序的最坏时间为 O(n log n),其缓存访问和比较搬移成本应与实际快排实现一起测量。

89的实现比较节点与存在的两个子节点,将较大者换到父位置并递归修复受影响分支;buildHeap从 n/2−1 递减到0,排序每次将堆顶换到末尾,再对缩短后的堆调用heapify。子节点索引是 int,极大输入需避免 2*idx+2 溢出。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 4 处

    • · 查看原书依据

      堆的性质 树中每一个节点的值都大于或者等于任意一个子节点的值(如果有的话)。 图4-15标记为a的堆就满足这些性质。二叉树的根节点的值必须是树中最大的,但是,注意到最小的元素可以是任何一个叶子节点。虽然二叉树的有序信息受限于这样一个事实:一个节点大于任意一个子节点。堆排序表明了如何利用这个外形的性质

    • · 查看原书依据

      稳定的排序。因为它非常频繁地移动元素,所以它不能使用基于值的数据。

    • · 查看原书依据

      快排性能退化的令人讨厌的(大都是令人尴尬的!)情况。尽管如此,平均情况下,快速排序比堆排序表现要好。

    • · 查看原书依据

      heapify函数。它要使用两个不同的空间,虽然都是为一个共同的目的。

    参考来源

    - 位置:《算法技术手册》第4章《堆排序》(spine1513;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1476.html;u086-ch04-020)。 - 结论依据:86全文、03211–03213伪代码与图,以及03185取整符号实读。 - 原始内容:堆的性质 树中每一个节点的值都大于或者等于任意一个子节点的值(如果有的话)。 图4-15标记为a的堆就满足这些性质。二叉树的根节点的值必须是树中最大的,但是,注意到最小的元素可以是任何一个叶子节点。虽然二叉树的有序信息受限于这样一个事实:一个节点大于任意一个子节点。堆排序表明了如何利用这个外形的性质 - 位置:《算法技术手册》第4章《使用环境》(spine1513;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1476.html;u087-ch04-020)。 - 结论依据:87指出堆排序不稳定;频繁交换大记录可能昂贵,但这不意味着不能对值类型排序。可按应用权衡直接移动值、交换指针或排序索引,并注意间接访问和额外存储成本。 - 原始内容:稳定的排序。因为它非常频繁地移动元素,所以它不能使用基于值的数据。 - 位置:《算法技术手册》第4章《驱动因素》(spine1514;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1477.html;u088-ch04-020)。 - 结论依据:88指出堆排序避开普通快排的二次最坏情形,但两者平均性能依环境而异。堆排序的最坏时间为 O(n log n),其缓存访问和比较搬移成本应与实际快排实现一起测量。 - 原始内容:快排性能退化的令人讨厌的(大都是令人尴尬的!)情况。尽管如此,平均情况下,快速排序比堆排序表现要好。 - 位置:《算法技术手册》第4章《解决方案》(spine1515;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1478.html;u089-ch04-020)。 - 结论依据:89的实现比较节点与存在的两个子节点,将较大者换到父位置并递归修复受影响分支;buildHeap从 n/2−1 递减到0,排序每次将堆顶换到末尾,再对缩短后的堆调用heapify。子节点索引是 int,极大输入需避免 2*idx+2 溢出。 - 原始内容:heapify函数。它要使用两个不同的空间,虽然都是为一个共同的目的。