Problem 1 (教材习题 6.1-1 和 6.1-2)
证明:含 n 个元素的堆的高度为 ⌊logn⌋ 。
Solution
证明:设含 n 个元素的堆的高度为 h 。
考虑高度为 h 的堆,它的结点数
最多是一个满二叉树的情况,有 1+2+⋯+2h=2h+1−1 个结点;
最少是一个高度为 h−1 的满二叉树再多 1 个元素在第 h 层的情况,有 1+2+⋯+2h−1+1=2h 个结点。
因此,我们找出了结点数和高度之间的不等式关系:
n≤2h+1−1⇒h≥log(n+1)−1>logn−1
n≥2h⇒h≤logn
即 logn−1<h≤logn ,也就是 h=⌊logn⌋ 。
Problem 2 (教材习题 6.1-7)
证明:当用数组表示存储 n 个元素的堆时,叶结点下标分别是
⌊n/2⌋+1,⌊n/2⌋+2,⋯,n
Solution
证明:根据完全二叉树的定义,叶结点的下标连续是显然的。我们只需要证明叶结点的下标最小是 ⌊n/2⌋+1 即可。
假设最小的叶结点的下标是 k 则
- 由于这是叶结点——没有子结点,我们有 LEFT(k)≥n+1 ,即
k≥(n+1)/2>n/2
- 由于这是最小的叶结点,则 k−1 不是叶结点,因此 LEFT(k−1)≤n ,即
k≤n/2+1
综上,我们有 n/2−1<k−1≤n/2 ,即 k−1=⌊n/2⌋ ,也就是最小的叶结点下标为 k=⌊n/2⌋+1 。
Problem 3 (教材习题 6.2-2)
参考过程 MAX-HEAPIFY (见第3讲PPT第13页),写出能够维护相应最小堆的 MIN-HEAPIFY(A,i) 的伪代码,并比较 MIN-HEAPIFY 与 MAX-HEAPIFY 的运行时间。
Solution
不难看出, MIN-HEAPIFY 的运行时间和 MAX-HEAPIFY 是一样的,都是 O(h)=O(logn) ,其中 h 是以 A[i] 为根结点的子树高度。
Problem 4 (教材习题 6.2-6)
证明:对一个大小为 n 的堆, MAX-HEAPIFY 的最坏情况运行时间为 Ω(logn) 。(提示:对于 n 个结点的堆,可以通过对每个结点设定恰当的值,使得从根结点到叶结点路径上的每个结点都会递归调用 MAX-HEAPIFY 。)
Solution
证明:考虑情况 A[1]=0 , A[i]=1,2≤i≤n 。
由于 0 是 A[1..n] 中最小的元素,所以调用 MAX-HEAPIFY(A,1) 时,它需要和堆的每一层都交换,从而到达一个叶结点(这也是满足最大堆性质的情况下它应该在的位置)。
而堆的高度为 ⌊logn⌋ ,因此 MAX-HEAPIFY 在最坏情况下的运行时间为 Ω(logn) 。
因此,我们在第5讲PPT第13页给出的 MAX-HEAPIFY(A,1) 的上界 O(logn) 是一个紧确的界。
Problem 5 (教材习题 6.3-2)
对于 BUILD-MAX 中第 2 行的循环控制变量 i 来说,为什么我们要求它是从 ⌊A.length/2⌋ 到 1 递减,而不是从 1 到 ⌊A.length/2⌋ 递增呢?
Solution
这是因为 MAX-HEAPIFY 算法的输入 i 能够维护最大堆性质的前提是 LEFT(i) 和 RIGHT(i) 已经满足最大堆性质。从后往前迭代是因为最后的叶结点本身就是平凡的最大堆,能够满足让 MAX-HEAPIFY 成立的输入条件。
基于循环不变式的算法正确性证明详见第5讲PPT第18页。
Problem 6 (教材习题 6.3-3)
证明:对于任一包含 n 个元素的堆中,至多有 ⌈n/2h+1⌋ 个高度为 h 的结点。
Solution
证明:记高度为 h 的结点有 nh 个,下面证明 nh≤⌈n/2h+1⌋ 。对 h 进行归纳。
基础情况: h=0 时显然成立,根据练习5-1问题2,一个包含 n 个元素的堆有 ⌈n/2⌉ 个叶结点,也就是 n0≤⌈n/20+1⌉ 。
归纳假设:假设高度为 nh−1⌈n/2h⌉ 。
归纳步骤:下面证明 nh≤⌈n/2h+1⌉ 。
如果 nh−1 是偶数,则 nh=nh−1/2=⌈nh−1/2⌉ ;
如果 nh−1 是奇数,则 nh=⌊nh−1/2⌋+1=⌈nh−1/2⌉ ;
- 高度为 h 的结点中 nh−1 个结点有两个孩子, 1 个结点有一个孩子。
结合上述两种情况,我们有 nh=⌈nh−1/2⌉ ,于是
nh=⌈2nh−1⌉≤⌈21⋅⌈2hn⌉⌉=⌈⌈2h+1n⌉⌉=⌈2h+1n⌉
综上, nh≤⌈n/2h+1⌉ 。
Problem 7 (教材习题 6.4-2)
试分析在使用下列循环不变式时, HEAPSORT (详见第5讲PPT第21页)的正确性:
在算法的第 2 到 5 行 for 循环每次迭代开始时,子数组 A[1..i] 是一个包含了数组 A[1..n] 中前 i 小元素的最大堆,而子数组 A[i+1..n] 包含了数组 A[1..n] 中已排好序的前 n−i 大元素。
Solution
证明:采用“初始化-保持-终止”的方法来证明不变式,并说明堆排序的正确性。
初始化:第一次迭代之前,i=n ,根据算法第 1 行 BUILD-MAX-HEAP(A) 的正确性,显然有子数组 A[1..n] 包含了数组 A[1..n] 中前 n 小元素的最大堆,而子数组 A[n+1..n] 包含了数组 A[1..n] 中已经排好序的前 n−n=0 大元素。
保持:假设迭代开始前,子数组 A[1..i] 是一个包含了数组 A[1..n] 中前 i 小元素的最大堆,而子数组 A[i+1..n] 包含了数组 A[1..n] 中已排好序的前 n−i 大元素。
A[1] 是 A[1..i] 中的最大元素,但是比 A[i+1..n] 都小,算法第3行将其与 A[i] 交换,此时 A[i] 比 A[i+1..n] 都小且是 A[1..i] 中的最大元素。而 A[i+1..n] 本身是排好序的,因此,在前面多缀了一个更小元素 A[i] 的 A[i..n] 依旧是排好序的,且是前 n−i+1 大元素。
算法第 4 行将堆的大小减 1 ,得到了新的堆 A[1..i−1] 。之前交换 A[1] 和 A[i] 的操作并没有破坏 A[2] 和 A[3] 在 A[1..i−1] 中对应子树的最大堆性质,因此算法第 5 行的 MAX-HEAPIFY(A,1) 能够维护 A[1..i−1] 的最大堆性质。同时,由于我们踢出堆的是原本前 i 小的元素 A[1..i] 中的最大元素,因此现在的 A[1..i−1] 中是前 i−1 小元素。
综上,下一次迭代开始前,子数组 A[1..i−1] 是一个包含了数组 A[1..n] 中前 i−1 小元素的最大堆,而子数组 A[i..n] 包含了数组 A[1..n] 中已排好序的前 n−i+1 大元素。循环保持了不变式。
终止:最后一次迭代结束后,i=1 ,根据循环不变式,我们有 A[2..n] 包含了数组 A[1..n] 中已经排好序的前 n−1 大元素,A[1] 是 A[1..n] 中第 1 小,也就是最小的元素。
综上,算法结束时 A[1..n] 已经排好了序,堆排序算法的正确性得证。