6.1 堆

6.1-1

解：2h+1−12^{h+1}-12h+1−1;2h+12^h+12h+1

6.1-2

证明：

2h≤n≤2h+1−1&lt;2h+12^h\leq n\leq 2^{h+1}-1&lt;2^{h+1}2h≤n≤2h+1−1<2h+1

h≤lg⁡n&lt;h+1h\leq\lg n&lt;h+1h≤lgn<h+1

h=⌊lg⁡n⌋h=\lfloor\lg n\rfloorh=⌊lgn⌋

6.1-3

由最大堆性质可知。

6.1-4

解：叶子结点。

6.1-5

解：升序的话，是。

6.1-6

解：不是。

6.1-7

解：n是最后一个元素→n的父结点是最后一个父结点且n的父结点为⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋→结论。

6.2 维护堆的性质

6.2-1

解：⟨27,17,3,16,13,10,1,5,7,12,4,8,9,0⟩⟨27,17,10,16,13,3,1,5,7,12,4,8,9,0⟩⟨27,17,10,16,13,9,1,5,7,12,4,8,3,0⟩\begin{aligned} \langle 27, 17, 3, 16, 13, 10,1, 5, 7, 12, 4, 8, 9, 0 \rangle \\ \langle 27, 17, 10, 16, 13, 3, 1, 5, 7, 12, 4, 8, 9, 0 \rangle \\ \langle 27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0 \rangle \\ \end{aligned} ⟨27,17,3,16,13,10,1,5,7,12,4,8,9,0⟩⟨27,17,10,16,13,3,1,5,7,12,4,8,9,0⟩⟨27,17,10,16,13,9,1,5,7,12,4,8,3,0⟩​

6.2-2

MIN-HEAPIFY(A, i)l = LEFT(i)r = RIGHT(i)if l <= A.heap-size and A[l] < A[i]smallest = lelse smallest = iif r <= A.heap-size and A[r] < A[smallest]smallest = rif smallest !=iexchange A[i] with A[smallest]MIN-HEAPIFY(A, smallest)

运行时间相等。

6.2-3

解：自动退出。

6.2-4

解：自动退出。

6.2-5

解：

MAX-HEAPIFY(A, i)while i <= A.length / 2l = LEFT(i)r = RIGHT(i)if l <= A.heap-size and A[l] > A[i]largest = lelse largest = iif r <= A.heap-size and A[r] > A[largest]largest = rif largest != iexchange A[i] with A[largest]i = largest

6.2-6

证明（来自参考答案）：

If you put a value at the root that is less than every value in the left and right subtrees, then MAX-HEAPIFY\text{MAX-HEAPIFY}MAX-HEAPIFY will be called recursively until a leaf is reached. To make the recursive calls traverse the longest path to a leaf, choose values that make MAX-HEAPIFY\text{MAX-HEAPIFY}MAX-HEAPIFY always recurse on the left child. It follows the left branch when the left child is greater than or equal to the right child, so putting 000 at the root and 111 at all the other nodes, for example, will accomplish that. With such values, MAX-HEAPIFY\text{MAX-HEAPIFY}MAX-HEAPIFY will be called hhh times (where hhh is the heap height, which is the number of edges in the longest path from the root to a leaf), so its running time will be Θ(h)\Theta(h)Θ(h) (since each call does Θ(1)\Theta(1)Θ(1) work), which is Θ(lg⁡n)\Theta(\lg n)Θ(lgn). Since we have a case in which MAX-HEAPIFY\text{MAX-HEAPIFY}MAX-HEAPIFY's running time is Θ(lg⁡n)\Theta(\lg n)Θ(lgn), its worst-case running time is Ω(lg⁡n)\Omega(\lg n)Ω(lgn).

6.3 建堆

6.3-1

略。。。

6.3-2

思路：因为MAX-HEAPIFY的前提是左右均为最大堆，如果递增岂不是一开始就是最大堆？

6.3-3

思路：可使用归纳法证明。

6.4 堆排序算法

6.4-1

6.4-2

证明：

初始化：子数组A[i+1…n]为空，因此不变式成立。

保持：A[1]是A[1…i]中的最大元素，它小于A[i+1…n]中的元素。当我们把它放在第i个位置时，A[i…n]包含最大的元素，且已排好序。减小堆大小并调用MAX-HEAPIFY将A[1…i-1]转换为最大堆。递减i为下一次迭代设置不变量。

终止：循环后i=1。这意味着A[2…n]被排序，A[1]是数组中的最小元素，这使得数组被排序。

6.4-3

解：Θ(nlg⁡n)\Theta(n\lg n)Θ(nlgn);Θ(nlg⁡n)\Theta(n\lg n)Θ(nlgn)

6.4-4

由6.4-3可得。

6.4-5

证明（来自参考答案）：

This proved to be quite tricky. My initial solution was wrong. Also, heapsort appeared in 1964, but the lower bound was proved by Schaffer and Sedgewick in 1992. It’s evil to put this an exercise.

Let’s assume that the heap is a full binary tree with n=2k−1n = 2^k - 1n=2k−1. There are 2k−12^{k - 1}2k−1 leaves and 2k−1−12^{k - 1} - 12k−1−1 inner nodes.

Let’s look at sorting the first 2k−12^{k - 1}2k−1 elements of the heap. Let’s consider their arrangement in the heap and color the leaves to be red and the inner nodes to be blue. The colored nodes are a subtree of the heap (otherwise there would be a contradiction). Since there are 2k−12^{k - 1}2k−1 colored nodes, at most 2k−22^{k - 2}2k−2 are red, which means that at least 2k−2−12^{k - 2} - 12k−2−1 are blue.

While the red nodes can jump directly to the root, the blue nodes need to travel up before they get removed. Let’s count the number of swaps to move the blue nodes to the root. The minimal case of swaps is when (1) there are 2k−2−12^{k - 2} - 12k−2−1 blue nodes and (2) they are arranged in a binary tree. If there are ddd such blue nodes, then there would be i=lg⁡di = \lg di=lgd levels, each containing 2i2^i2i nodes with length iii. Thus the number of swaps is,

∑i=0lg⁡di2i=2+(lg⁡d−2)2lg⁡d=Ω(dlg⁡d).\sum_{i = 0}^{\lg d}i2^i = 2 + (\lg d - 2)2^{\lg d} = \Omega(d\lg d).i=0∑lgd​i2i=2+(lgd−2)2lgd=Ω(dlgd).

And now for a lazy (but cute) trick. We’ve figured out a tight bound on sorting half of the heap. We have the following recurrence:

T(n)=T(n/2)+Ω(nlg⁡n).T(n) = T(n / 2) + \Omega(n\lg n).T(n)=T(n/2)+Ω(nlgn).

Applying the master method, we get that T(n)=Ω(nlg⁡n)T(n) = \Omega(n\lg n)T(n)=Ω(nlgn).

6.5 优先队列

6.5-1

略。。。

6.5-2

6.5-3

解：

HEAP-MINIMUM(A)return A[1]

HEAP-EXTRACT-MIN(A)if A.heap-size < 1error "heap underflow"min = A[1]A[1] = A[A.heap-size]A.heap-size = A.heap-size - 1MIN-HEAPIFY(A, 1)return min

HEAP-DECREASE-KEY(A, i, key)if key > A[i]error "new key is larger than current key"A[i] = keywhile i > 1 and A[PARENT(i)] > A[i]exchange A[i] with A[PARENT(i)]i = PARENT(i)

MIN-HEAP-INSERT(A, key)A.heap-size = A.heap-size + 1A[heap-size] = ∞HEAP-DECREASE-KEY(A, A.heap-size, key)

6.5-4

解：保证key>A[A.heap-size]

6.5-5

证明：

初始化：A是一个堆，除了A[i]可能比它的父结点更大，因为它已被修改。A[i]比其子节点大，因为否则警戒将失败并且不会输入循环（新值大于旧值并且旧值大于子节点）。

保持：当我们用父结点交换A[i]时，除了A[PARENT(i)]可能比它的父结点更大之外，满足最大堆属性。 将i更改为其父结点会保持不变量。

终止：每当堆耗尽或A[i]及其父结点的最大堆属性被保留时，循环就会终止。在循环终止时，A是最大堆。

6.5-6

解：

HEAP-INCREASE-KEY(A, i, key)if key < A[i]error "new key is small than current key"A[i] = keywhile i > 1 and A[PARENT(i)] < keyA[i] = A[PARENT(i)]i = PARENT(i)A[i] = key

6.5-7

解：

队列：将HEAP-EXTRACT-MAX改为HEAP-EXTRACT-MIN。

栈：INSERT时保证值最大。

6.5-8

解：

HEAP-DELETE(A, i):A[i] = A[A.heap-size]A.heap-size = A.heap-size - 1MAX-HEAPIFY(A, i)

6.5-9

思路：取各链表第一个元素建最小堆。

思考题

6-1 （用插入的方法建堆）

a.

解：否；假设输入数据为1，2，3……

b.

证明思路：MAX_HEAP_INSERT是一个Θ(lgn)的操作，并需要调用Θ(n)次。

6-2 （对d叉堆的分析）

a.

解：

PARENT(i) = ⌊i/d⌋，当i mod d = 0, 1

PARENT(i) = ⌈i/d⌉，当i mod d = 2, … , d-1

CHILD(i) = di-d+2, … , di+1

b.

解：⌈logd[n(d-1)+1]⌉

c.

解：

EXTRACT-MAX(A)if A.heap-size < 1error "heap underflow"max = A[1]A[1] = A[A.heap-size]A.heap-size = A.heap-size - 1MAX-HEAPIFY(A, 1, d) // 此处d为叉数return max

MAX-HEAPIFY(A, i, d)largest = ifor k = di-d+2 to di+1if k <= A.heap-size and A[k] > A[largest]largest = kif larget != iexchange A[i] with A[largest]MAX-HEAPIFY(A, largest, d)

O(dlogdn)

d.

解：

INSERT(A, key)A.heap-size = A.heap-size + 1A[A.heap-size] = -∞INCREASE-KEY(A, A.heap-size, key)

O(logdn)

e.

解：

INCREASE-KEY(A, i, key)if key < A[i]error "new key is smaller than current key"A[i] = keywhile i > 1 and A[PARENT(i)] < A[i]exchange A[i] with A[PARENT(i)]i = PARENT(i)

O(logdn)

6-3 （Young氏矩阵）

a.

解：

2 3 4 5

8 9 12 14

16 ∞ ∞ ∞

∞ ∞ ∞ ∞

b.

证明思路：可以先对行（或列）使用归纳法进行证明，再扩展至另一维度。

c.

解：

EXTRACT-MIN(A, m, n)if m < 1 or n < 1error "matrix underflow"min = A[1, 1]A[1, 1] = A[m, n]A[m, n] = ∞ MIN-MATRIX(A, m-1, n) // or (A, m, n-1)

MIN-MATRIX(A, m, n, x, y)smallest = A[x, y]smallest_x = xsmallest_y = yif x + 1 <=m and A[x+1, y] < smallestsmallest = A[x+1, y]smallest_x = x + 1if y + 1 <= n and A[x, y+1] < smallestsmallest = A[x, y+1]smallest_x = xsmallest_y = y + 1if smallest != A[x, y]exchange A[x, y] with A[smallest_x, smallest_y]MIN_MATRIX(A, m, n, smallest_x, smallest_y)

d.

解：

MATRIX-INSERT(A, m, n, key)A[m, n] = keyx = my = nwhile (x > 1 or y > 1) and flag == 0flag = 1if x >= 2 and A[x-1, y] > A[x, y]larger_x = x - 1larger_y = yflag = 0if n >= 2 and A[x, y-1] > A[larger_x, larger_y]larger_x = xlarger_y = y - 1flag = 0if flag == 0exchange A[x, y] with A[larger_x, larger_y]x = larger_xy = larger_y

e.

解：

YOUNG-MATRIX-SORT(A, m, n)let B be a new arrayfor i = 1 to n^2B[i] = EXTRACT-MIN(A)

n2·O(m+n) = n2·O(2n) = O(n3)

f.

思路：从矩阵的右上方（或左下方）开始比较，如果矩阵中的元素比较大，就继续向左（向上）比较，反之则向下（向右）比较。

解：

YOUNG-MATRIX-SEARCH(A, m, n, key)x = my = 1while x >1 and y < nif A[x, y] == keyreturn x, yelse if A[x, y] < keyy = y + 1else x = x - 1return NIL