优先队列不是排序数组
最小优先队列保存可比较键值的多重集合,支持插入及移除一个最小键值;空队列的移除操作报告下溢。键值可以相等。二叉最小堆提供这些操作,但不要求整个数组有序;对相等键值,它本身也不保证先进先出。
定义 3.1.1
(二叉最小堆)
使用连续数组的一基位置 。对 ,其父节点是 ;可能的子节点是 和 ,前提是索引不超过 。若堆不变量成立,该数组就是最小堆:
索引规则使其形状为完全二叉树:每层从左至右填满。从任一索引沿父节点最终到达 ,由不变量知, 时 是最小值。数组不必递增: 是最小堆,虽然 。
概念视角结构
把位置看成二进制串
把每个位置写成二进制。位置 是根;位置 的子节点 和 ,就是在 的二进制串后面加上 或 。父节点 则是删去最后一位。例如 的父节点是 ,深度 。位置 的深度是位数减一,而深度为 的位置都至少是 。这个对同一棵树的描述,同时解释了完全树形状和下文使用的对数高度。
假设比较键值及数组访问都需常数时间。以下界限在已分配足够容量下计算比较和移动;若数组扩容时需复制全部元素,该分配成本必须另行分析。
插入:向上修补路径
把新键值加到位置 ,再反复与父节点比较。若严格较小,就交换并在父位置继续;否则停止。相等时不需交换。
定理 3.1.2
(插入保持堆不变量)
设 是最小堆, 是一个键值。把 加在末端,并在它严格小于父节点时不断上移,所得结果是一个最小堆,所含的键值是原有键值连同 。
证明
(沿向上路径的循环不变量)
令 为当前存放 的位置。断言:(i) 所有不以 为终点的父子边都符合不变量;(ii) 若 有父节点 ,则对 的每个子节点 都有 。起初 是叶节点,所以 (ii) 为空,而所有旧边都有序。
若 或 ,循环停止,唯一可能出错的边(以 为终点的边)已有序,所以数组是堆。否则 ,我们交换。新边 有序,因为 。对 的子节点 ,由 (ii) 知 ,所以边 有序。对 的兄弟 ,由旧边 得 ,所以边 有序。最后, 现在位于 。设 为 的父节点(若存在)。旧边 给出 ,而 ,所以 不大于 的两个子节点,这就是 处的 (ii);仍可能出错的只有以 为终点的边。位置每步递减,所以循环会结束。交换保留多重集合,而追加操作保留完全树形状。
例题 3.1.3
(把 1 插入六项的堆)
把 插入 。先加在位置 ,与 交换,再与 交换:
键值停在根,即位置 。多重集合是原来的加上 。
移除最小值:向下修补路径
若 ,返回唯一元素并清空数组。若 ,保存并返回根,把最后键值移到位置 ,并把数组缩短一项。之后只要当前节点有比它小的子节点,就与较小的子节点交换;两者相等可任选。然后从该子节点原位置继续。到达叶节点或当前键值不大于任何现有子节点时停止。
定理 3.1.4
(移除最小值)
设 是最小堆,。上述过程返回一个最小键值,并留下一个存放其余 个键值的最小堆。
证明
(沿向下路径的循环不变量)
返回的根是最小值,因为由不变量知对所有 都有 。把最后键值 移到位置 后,根的两个子树仍是堆。令 为存放 的位置。断言:(i) 所有不以 为起点的边都有序;(ii) 若 有父节点 ,则对 的每个子节点 都有 。起初 ,所以 (ii) 为空。
若 没有比 小的子节点,从 出发的边都有序,数组是堆。否则令 为 的一个较小子节点,即 ,且对另一个子节点 有 。交换后,边 有序,因为由 (ii) 知 ; 有序,因为 ; 有序,因为 。 的子节点 在旧数组中满足 ,这表示 处的新值不大于 ,所以 (ii) 在 处成立,可能出错的只有从 出发的边。每步位置下降一层,所以循环在叶节点或停止判断处结束。移除最后位置保留完全树形状。
证明透视
为何必须选较小的子节点
关键步骤是选择较小的子节点 。证明中只有一个不等式用到它: 使交换后通往兄弟的边有序,其余部分对任一子节点都成立。条件 (ii) 保证 上方的边安全:新值 来自 之下,所以至少是 。循环会结束,因为位置严格增加;它在被移动的键值到达叶节点,或没有子节点更小时完结。相等的情形不需特别处理,因为任一子节点都满足 。
反例模式
与较大的子节点交换
断言:删除时,只要与任何比被移动键值小的子节点交换即可。取堆 并移除最小值。最后键值 移到根,得到 ,两个子节点都小于 。与较大的子节点 交换,得到 。位置 是叶节点,循环停止,但根 大于其子节点 :结果不是堆。与较小的子节点 交换,得到 ;位置 没有子节点,且 、,所以这是堆。规则必须指明较小的子节点,这样上移的键值才不大于其兄弟。
例题 3.1.5
(在该插入之后移除最小值)
从 移除最小值,返回 ,并把最后键值 移到根,得到 。较小子节点是 ,交换一次得到 。此时 在位置 ,其唯一子节点 较大,所以循环停止。
高度与操作成本
定理 3.1.6
(对数高度与成本)
有 个元素的堆,高度至多为 。插入至多交换 次。移除至多交换 次,至多访问 个位置,每个位置至多作两次键值比较。
证明
(逐层计数)
在深度 的索引均至少为 ,这由二进制串的描述可见。索引至多为 ,所以 ,即 。插入从位置 开始,其深度至多为 ,每次交换上移一层。 时,移除作用于 个元素,其高度至多为 ;它从根开始,每次交换下移一层。在每个访问的位置,先比较两个子节点,再把较小者与该键值比较。有效数组占用 空间。
令 为操作前大小,在上述容量假设下,每次操作因此耗时 。非空堆只读最小值需 。这些是上述操作的界限,并未证明特定批量建堆方法或稳定的优先次序。
例题 3.1.7
(相等键值与只有一项的堆)
从 移除最小值。保存 ,把最后键值 移到根并缩短数组:。根有较小的子节点 ,交换得 ,是堆。再把 插入 :加在位置 得 ;其父节点(位置 )是 ,新键值并非严格较小,所以不交换。边界情形 :移除时返回唯一键值并留下空数组;对空数组则报告下溢。
常见错误
(以为第二小的键值在位置 2)
只有 保证是最小值。在堆 中,位置 是 ,但第二小的键值是 ,在位置 。不变量只把每个键值与其父节点比较,所以根的两个子节点之间并没有次序。
常见错误
(零基数组使用一基的子节点公式)
零基位置时, 的子节点是 和 。若仍用 和 ,位置 会成为自己的子节点,位置 的子节点会是 和 ,而非正确的 和 。应先固定一种约定,再由它推导父节点和子节点公式。
习题与解答
快速检查
(检查不变量。 是最小堆吗?)
把每个位置与其父节点比较。
解答 · 答案
不是:位置 的键值 大于其位置 的子键值 。
快速检查
(相等键值。 可以是最小堆吗?)
不变量要求哪些比较?
解答 · 答案
可以。两个父子比较均非严格,两份最小值可任选其一先移除。
快速检查
(删除。用上述方法从 移除最小值。)
先把最后键值移到根。
解答 · 答案
把 移到根得到 ;与较小子节点 交换,得到 。
快速检查
(下溢。从空堆移除时应怎样?)
有没有根键值可返回?
解答 · 答案
报告下溢,因为没有根键值可返回。一项的情形则返回该键值并留下空堆。