批量构造问题
前一节介绍最小堆及单次优先队列操作。本节输入为一个含 个键值的任意数组,键值来自全序集合;目标是把它重排成最小堆,而不遗失或复制键值。使用从一开始索引的数组 。当索引不超过 ,索引 的子节点为 和 。最小堆要求每个父节点的键值不大于每个现有子节点。空数组及单元素数组已符合此性质。
逐个插入所有键值可用 次比较。自底向上的构造则依次在索引 执行下滤。所有更大的索引都是叶节点。我们使用确定的约定:选取较小的子节点;若两个子键值相等则选左子节点;若父键值已不大于所选子键值便停止。
下滤及其前提
定义 3.2.1
(索引处的近似堆)
若 的现有子节点为根的子树都是最小堆,而 本身的键值却可能大于某个子键值,就称数组在 处是近似堆。节点 的高度 ,是在完整数组树中由 向下的最长路径所含的边数。
在 下滤时,假设数组在 处是近似堆。若 没有子节点便停止。否则选较小的现有子节点 。若 ,便停止;因 是最小的子节点,根不大于两个子节点,而整棵子树已是堆。若 ,交换两个键值,并在 继续。
引理 3.2.2
(下滤修复近似堆)
若数组在 处是近似堆,则在 下滤至多交换 次后终止,使以 为根的子树成为键值不变的最小堆,且不改变其他位置。
证明
(把可能的违反向下移一层)
设当前索引 处近似堆条件成立, 为较小的子节点。若没有交换,根不大于两个子节点,而两棵子树都是堆,所以整棵子树是堆。若 并交换,旧键值 移到 , 移到 。交换前,由子树是堆的假设, 不大于其自己的子节点;由选取方式,它也不大于兄弟节点。交换后,它成为 的新根,且不大于两个子节点:移下的旧父键值严格较大,兄弟节点原本也不小于 。未触及的子树仍是堆。只有以 为根的子树可能违反堆次序,而它的两棵子树仍是堆,所以近似堆条件在 处成立。索引严格向下移动,因此过程至多交换 次,并在叶节点或已符合条件的根停下。交换保持键值多重集不变,并只触及该子树内的位置。
证明透视
子树是堆的假设用在哪里
两棵子树都是堆这个假设,每次交换用一次:用来确定上移的键值 不大于 之下的一切。选较小子节点则用一次:用来确定它也不大于兄弟。若其中一项不成立, 处的新根仍可能大于其下的某个键值,单次向下走便不够。这条路径会终止,因为索引严格增加;它在叶节点,或在键值已不大于其较小子节点的节点处完结。
定理 3.2.3
(自底向上构造是正确的)
按递减次序处理索引 ,并各自下滤,可把任何数组变成恰好含原有键值的最小堆。
证明
(对递减索引作归纳)
在处理 之前,每个子节点的索引较大,其子树已是堆:它不是叶节点,就是其下滤已较早完成,而且之后没有任何下滤改变过它的子树,因为每次下滤只改变自己索引的子树,而严格介于 与该子节点之间的索引都不是该子节点的祖先。所以数组在 处是近似堆, 的下滤使以 为根的子树成为堆。归纳至 ,便证明最终数组是最小堆,且恰好保留原有键值。不保证相等键值之间的稳定次序。
反例模式
按递增次序处理索引
断言:按哪个次序处理索引 都没有关系。取 ,按 的次序下滤。在索引 , 先与较小子节点 交换,再与其新位置 的较小子节点 交换,得到 。在索引 ,键值 不大于其子节点 和 ,没有变化。在索引 , 与 交换,得到 。根 大于其子节点 ,所以结果不是堆。在索引 时,子节点为根的子树还不是堆,前提不成立;递减次序正好保证前提成立。
为何构造是线性时间
定理 3.2.4
(建堆的线性界)
当 ,所有节点高度之和满足 。因此自底向上构造总共少于 次交换,并使用 次键值比较。
证明
(按高度为节点计数)
由 开始下滤至多向下交换 次。节点高度至少为 ,当且仅当其最左可能后代索引 存在,因此此类节点至多有 个。对可能的向下层数作双重计数,得到
最后的和是有限和,因为各项最终为零。每层至多使用常数次键值比较,而循环至多启动 次下滤;故在比较及存取均为常数时间的模型下,整体构造使用 次比较和交换。当 ,循环不执行。
数组原地重用,因此迭代式下滤只需 额外空间。此界是建立堆的成本,不是完整排序数组的成本。
追踪例子
例题 3.2.5
(七个键值的数组)
从 开始。最后一个非叶节点的索引是 。
| 处理索引 | 下滤后的数组 |
|---|---|
| 3 | |
| 2 | |
| 1 |
在索引 ,键值 先与 交换,再与 交换。最终根是最小值,但兄弟节点及子树一般没有整体排序。
例题 3.2.6
(n = 7 时的交换次数)
节点 的高度为 ,总和 。这与计数论证吻合:高度至少为 要求 ,共三个节点;高度至少为 要求 ,一个节点;高度至少为 要求 ,没有节点。在上面的追踪中,各次下滤交换了 次,所以每次下滤都用尽其高度,交换次数等于 。
例题 3.2.7
(相等键值与很小的输入)
对 ,只有索引 是非叶节点。两个子节点键值同为 ,左子节点规则选索引 ;因 而交换,得 。若改选右子节点,则得 ;两者都是堆。对 ,索引 只有索引 一个子节点, 得 。当 或 ,没有非叶索引,数组不变。
常见错误
(把堆当成已排序的数组)
第一个追踪的结果 是有效的堆,但没有排序:位置 的 大于位置 的 。堆只保证每个键值不大于其子节点,所以只知道根是最小值。要得到已排序的输出,还需要更多工作。
习题
快速检查
(对 套用上述约定,给出处理索引 、、 后各自的数组。)
索引 只有索引 一个子节点。
解答 · 答案
数组依次为 、、。
快速检查
(以子键值相等时选左方的规则,从 建堆。为何改变平局规则后,即使结果数组可能不同,正确性仍保持?)
比较两个相等的子节点作为候选。
解答 · 答案
结果为 。两个相等子节点任选其一都是最小子节点,因此局部堆论证仍适用;相等键值的次序不一定稳定。
快速检查
(解释为何把每次下滤分别界定为 ,只能证明 ;指出得到较精确上界所需的额外事实。)
有多少个节点是很高的?
解答 · 答案
该估计向每个节点都收取最大可能高度的成本。高度至少为 的节点至多有 个,故把实际高度界相加,总向下层数少于 。