知识卡片
最大堆用数组表示完全二叉树
最大堆满足两个条件:树是完全二叉树,且每个父节点不小于其子节点。根节点因此是最大值,但兄弟之间和不同分支不必有序。零基数组中节点 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函数。它要使用两个不同的空间,虽然都是为一个共同的目的。