动机
已排序的数组记录了每一对键之间的顺序。堆记录的信息较少:每个父结点都支配其子结点,因此无需对其余键排序,也能轻易找到最大键。这种偏序支持反复取出最大元素,也支持一种直接使用输入数组本身作为存储的排序算法。
出人意料的是建堆的代价。对单个顶点做下沉可能需要对数时间,但对每个顶点都建堆,总时间是线性的,而不是顶点数乘以对数。大多数顶点靠近叶子,可下移的距离很短。证明的方法是统计每种高度至多有多少个顶点,而不是让所有顶点都按根的最坏高度计费。
所有界都按常数代价的键比较和普通数组访问计算;若键的表示较昂贵,则必须把比较的代价计入。
定义
定义 8.2.1
(数组形状与最大堆序)
大小为 的堆占用数组的第一到第 个位置,具有完全二叉树的形状:位置 的子结点为 与 (在大小范围之内时),非根结点的父结点为 。数组按层从左到右填充。
最大堆要求在每一对父子之间都有 ,且只比较键。顶点的高度是它到后代叶子的最大边数。叶子的高度为零。当 时,根的高度至多为 。
活动堆可以只是更长数组的一个前缀;即使数组中存在超出当前大小的位置,那些位置上的子结点也要忽略。记录除键之外还可以带有身份标签。稳定排序保持键相等的记录的原有相对顺序,这一条件与数值上是否有序是分开的。
定义 8.2.2
(迭代式下沉)
假设所选位置的两棵子树都已经是堆。比较其现有子树的两个根,选取其中较大的一个。若该子结点的键大于当前键,则交换两者,并在该子结点的位置继续。否则停止。到达叶子时也停止。当两个子结点的键相等时,任何固定的选择规则都有效。每一步都以当前活动堆的边界为准。
下沉的实现只需用常数辅助空间保存当前下标、所选子结点下标和一条临时记录。递归版本还会额外使用调用栈;下文常数空间的排序结论使用的是这一迭代例程。
定理/命题
定理 8.2.3
(下沉修复单个根处的违例)
在上述子树假设下,下沉在所选整棵子树上产生一个堆,并保持其记录的多重集不变。对于起始高度 ,它的工作量为 ,每检验一层至多做两次键比较,向下交换不超过 次。
定理 8.2.4
(自底向上建堆是线性的)
对含 条记录的数组,依次在位置 上做下沉。结果是一个最大堆。建堆的总时间为 ,因为对非空输入有
空数组无需下沉,本身已是堆。
定理 8.2.5
(堆排序以固定后缀原地排序)
先在整个输入上建立最大堆。对活动大小 ,把根与位置 交换,将活动边界降为 ,并对新的根做下沉。最终数组按键非递减有序,且记录与输入相同。
对于键互不相同的输入,随着 增长,其最坏时间为 ;其迭代实现除输入数组外只使用 辅助空间。它一般是不稳定的。空数组与单条记录的情形不执行取出循环。
这一看似特别的存储优势只需要一个数组和一个变化的活动前缀边界。这并不是说无论编码如何,键值都能放进一个机器字。键相等的不同记录即使在比较顺序已经正确时也可能被移动。
证明思路或证明
证明
(下沉的正确性与代价)
对于下沉:堆的根沿父子链的传递性支配其整棵子树。因此较大的子树根支配该子树中的每个键,若还有另一个子结点,也支配另一个子树根。若当前键同时支配两个子树根,则所有父子约束都成立,过程正确停止。
否则与较大的子结点交换。新的顶部键支配原来的当前键以及原来的两棵子树。下移记录之上的所有约束现已正确;只有该记录的新位置可能违反其下方的顺序。它自己的子树未受影响,仍是堆,因此同样的论证可以重复。每次交换,当前下标严格下降,所以交换次数至多等于起始高度。在停止位置或叶子处,剩余的违例消失。交换完全保持记录不变。
每检验一层至多需要一次子结点之间的比较和一次与当前键的比较。在叶子之上仍会发生一次最后的不交换检验,它包含在原有的高度界之内。这证明了代价估计,其中包括高度为零时循环建立的常数开销。
证明
(为什么按下标递减建堆是线性的)
对于建堆:任何工作开始之前,每个叶子都是堆。按下标递减处理到下标 时,其子结点的位置更大,因此它们要么已被处理,要么是叶子。于是下沉的假设成立,由归纳法可知每个被处理的子树都是堆。最后对根的一步覆盖整棵树。
为统计工作量:下标为 、高度至少为 的顶点,其后代的下标至少为 ,因此必须满足 。所以高度至少为 的顶点至多有 个。对高度的指示量求和即得所示等式,而几何级数的上界小于 。每个被处理顶点的额外常数工作量同样是线性的。该证明使用了完全的数组树形状;它不能把同样的顶点数估计用于任意不平衡的二叉树。
证明透视
建堆对不同的高度求和,而不是用同一个最坏情形
关键一步是把求和次序颠倒:不是问每个顶点最多能下沉多远,而是问有多少个顶点能下沉至少 层。完全的数组形状只在一处使用,就是得出这种顶点必须满足 ;按下标递减的次序只用来提供下沉所需的假设,即两棵子树都已是堆。除此以外,键的取值并无影响。
计数这一步不能去掉形状假设。若二叉树是由 个顶点串成的一条路径,各顶点高度为 ,总和是 ,是平方阶。把每个顶点都乘以根的对数界,是有效但宽松的上界,错过了只有平衡形状才能提供的线性保证。
证明
(堆排序的不变式与运行时间)
对于堆排序,维持如下不变式:活动前缀是堆,后缀已排序,且每个活动键至多等于每个后缀键。起初后缀为空,建堆给出堆。根是活动记录中的一个最大值。把它与活动的最后一个位置交换,就把该最大值接到后缀之前,它不大于任何已固定的后缀键。去掉该位置后,前缀仍保持完全树的形状,只有它的新根可能违反堆序。下沉修复之。归纳法证明了所有步骤,最后剩下一条记录的前缀使有序性完整。记录得以保存,是因为整个过程只有交换。
建堆花费线性时间,至多 次取出步骤各花费 ,由此得到上界。对于键互不相同的比较排序,二叉判定树必须区分全部 种可能的相对顺序。其最坏深度至少为 ,由于最大的一半因子都至少为 ,这是 。已证明的正确性使堆排序受此下界约束,从而得到所述的最坏阶。这并不意味着每个含相等键的输入都要花这么长时间。
优先队列操作与内存分配假设
堆根可在常数时间内给出最大值。在数组容量足够时插入:把新记录追加到末尾,只要它大于其父结点就向上交换。只有这条祖先链可能出现新的违例;交换修复了它的下端边,并使可能的违例向根的方向移动。该链的长度是对数的。取出最大值时,用最后一条记录替换根,缩短堆;若仍有记录,则对根做下沉。子树仍是堆。当存储空间已经可用时,这些操作的最坏情形比较与访问代价都是对数的。
扩充底层数组可能另外复制所有记录。前面的界并不会使这次复制消失。倍增数组有前面已证明的另一个摊还保证,而某次触发扩容的插入在实际物理工作量上仍可能是线性的。大小固定的堆排序数组无需这种扩容,所以它的辅助空间分析与每次取出的分析都不受影响。
例题详解
例题 8.2.6
(六个键上的自底向上建堆)
从 开始。位置三已经支配它唯一的子结点。对位置二做下沉,把一与五交换,得到 。在根处,先把三与六交换,再在其新位置与四交换。结果是 。
兄弟键五和四之间无需按任何指定方向排序;它们各自只受自己的父结点和子结点约束。所得数组是堆,是因为五条父子不等式全部成立,而不是因为顺序读出这个数组会得到有序序列。
例题 8.2.7
(有序后缀在增长,而活动前缀在变化)
从该堆出发,把六与最后的三交换。活动前缀变为 ,固定后缀为六。下沉后得到活动前缀 。接着把五与活动的最后一个键二交换,并再次缩短;下沉后得到 ,其后是后缀 。
在检验子结点时必须排除后缀。它的大键已经处在最终位置;若允许它们回到活动堆中,就会破坏进展不变式。此时活动根四是剩余键中最大的,而不是整个数组中最大的。
例题 8.2.8
(插入与取出沿着一条根路径移动)
在容量足够的情况下,把七插入堆 。它被追加在位置七,与位置三的父结点四交换,再与根六交换。堆变为 。
取出七时,把最后的四移到根,并把堆缩短为六个元素。把该四与子结点六交换,又得到 。其他分支的堆不等式始终保持。只需找出并修复一条祖先路径或后代路径即可,因为操作之前的状态已经是堆。
概念视角结构
堆只存储回答它下一个问题所需的比较
父子序使最大值可以直接取得,同时让大多数兄弟与堂兄弟之间的比较保持未决。反复取出逐步确定出整个输出顺序。完全形状控制操作的深度,偏序的键序决定哪条记录可以被取出;只靠其中任何一个性质都不足以构成这个算法。
常见错误
反例模式
键相等的记录可能被最后的交换颠倒
取两条记录 ,输入顺序如此。因为键相等,建堆时它们保持原位。排序的取出步骤仍然交换根与最后一个位置,得到 。键被正确排序,但键相等的记录的身份顺序被颠倒,所以这种堆排序不是稳定的。稳定性是关于键相等时记录顺序的性质,而不仅仅是排序后键值的性质。
常见错误
(对子树尚未成堆的根做下沉)
下沉只把一条记录与它的两个子结点比较,所以它只修复顶部的违例,其他位置一概不管。取 ,位置二的一位于其子结点五和四之上。对位置一做下沉,是把三与较大的子结点二比较,没有发现违例就停止,结果仍是 。它不是堆,因为一在五之上。这就是建堆必须按下标递减进行的原因:这样每次下沉开始时,其两棵子树都已是堆。
常见错误
(让下沉看到已排序的后缀)
堆排序过程中活动边界不断缩小,边界之外的子结点必须忽略。把 的根与最后的活动键交换后,状态是 。把一下沉,得到 。若例程仍使用整个数组的长度,就会把一与它看似的子结点四和五比较,并与五交换,得到 ,其中后缀变成 ,不再有序。
堆数组不必整体有序。通过反复插入来建堆,其代价分析与自底向上建堆不同。递归的下沉例程并不会因为重用了数组本身就拥有常数的调用栈空间。在排序和优先队列更新的过程中,堆的大小与数组分配的长度必须保持区分。
总结
在两棵子树都是堆之后,下沉可以修复一个根。按下标递减建堆满足这一假设,而且是线性的,因为完全树中的顶点高度总和是线性的。堆排序反复把一个最大值放入固定的有序后缀,取出的工作量是对数的,迭代实现的辅助存储是常数,而键相等时的稳定性以及底层数组的分配仍各自有其独立条件。
练习
快速检查
(一棵完美二叉树的高度为 ,顶点数为 。计算所有顶点高度之和。)
利用每个正整数层级上高度至少为该层级的顶点个数。
解答 · 答案
对 ,恰有 个顶点的高度至少为 。求和得 。当 时结果为零,与单个叶子相符。即使根的高度增长,这一结果也使建堆的线性求和变得明确。
快速检查
(给出一个既不是递增也不是递减排列的最大堆数组。并解释为什么每个非递增数组都是最大堆。)
比较下标顺序与父子下标关系。
解答 · 答案
数组 是有效的最大堆,因为根五支配两个子结点。它不是非递减的,因为五大于三;也不是非递增的,因为三小于四。反之,在非递增数组中,每个父结点的下标都小于其各个子结点的下标,所以它的键至少等于子结点的键。因此全部堆不等式都成立。因此每个非递增数组都是堆,而其逆不成立。
快速检查
(从例题中的堆排序状态(活动前缀 、已排序后缀 )继续,直至完成。写出每次取出时的活动边界。)
不要下沉到固定的后缀中。
解答 · 答案
活动大小为四时,把根四与一交换,得到活动前缀 与后缀 。下沉后为 。活动大小为三时,把三与二交换,得到前缀 与后缀 ;它已经是堆。活动大小为二时,把二与一交换,剩下单个活动键一,后缀为 。完整的数组是 ,并且没有任何后缀项在被固定之后参与下沉。