算法导论6.5 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 2 分钟

6.5-1

用数组来表示这个堆的变化（横线标出变化之处）：

\(\begin{aligned} & \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1\rangle\\ & \langle \underline{1}, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2 \rangle\\ & \langle 13, \underline{1}, 9, 5, 12, 8, 7, 4, 0, 6, 2 \rangle\\ & \langle 13, 12, 9, 5, \underline{1}, 8, 7, 4, 0, 6, 2 \rangle\\ & \langle 13, 12, 9, 5, 6, 8, 7, 4, 0, \underline{1}, 2 \rangle\\ \end{aligned}\)

6.5-2

用数组来表示这个堆的变化（横线标出变化之处）：

\(\begin{aligned} & \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1\rangle\\ & \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1, \underline{-\infty} \rangle\\ & \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1, \underline{10} \rangle\\ & \langle 15, 13, 9, 5, 12, \underline{10}, 7, 4, 0, 6, 2, 1, 8 \rangle\\ & \langle 15, 13, \underline{10}, 5, 12, 9, 7, 4, 0, 6, 2, 1, 8 \rangle\\ \end{aligned}\)

6.5-3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
MIN-HEAP-MINIMUM(A)
  if A.heap-size < 1
    error “heap underflow”
  return A[1]

MIN-HEAP-EXTRACT-MIN(A)
  min = MIN-HEAP-MINIMUM(A)
  A[1] = A[A.heap-size]
  A.heap-size = A.heap-size – 1
  MIN-HEAPIFY(A, 1)
  return min

MIN-HEAP-INCREASE-KEY(A, x, k)
  if k > x.key
    error “new key is larger than current key”
  x.key = k
  find the index i in array A where object x occurs
  while i > 1 and A[PARENT(i)].key > A[i].key
  exchange A[i] with A[PARENT(i)], updating the information that maps priority queue objects to array indices
  i = PARENT(i)

MIN-HEAP-INSERT(A, x, n)
  if A.heap-size == n
    error “heap overflow”
  A.heap-size = A.heap-size + 1
  k = x.key
  x.key = ∞
  A[A.heap-size] = x
  map x to index heap-size in the array
  MIN-HEAP-INCREASE-KEY(A, x, k)

6.5-4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
MAX-HEAP-DECREASE-KEY(A, x, k)
  if k > x.key
    error “new key is larger than current key”
  x.key = k
  find the index i in array A where object x occurs
  while i <= ⌊A.heap-size / 2⌋
    l = LEFT(i)
    r = RIGHT(i)
    if l <= A.heap-size and A[l] > A[i]
      largest = l
    else largest = i
    if r <= A.heap-size and A[r] > A[largest]
      largest = r
    if largest ≠ i
      exchange A[i] with A[largest], updating the information that maps priority queue objects to array indices
      i = largest
    else
      break

6.5-5

为了方便复用MAX-HEAP-INCREASE-KEY中的代码，并且让其通过算法MAX-HEAP-INCREASE-KEY中的第一行合法性判断。

6.5-6

算法MAX-HEAP-INCREASE-KEY的第5-7行代码最终的目的是将过大的值逐步移向根节点，而算法MAX-HEAPIFY则是将一个过小的值移向叶节点，两者是完全不一样的功能，无法替代。

6.5-7

初始化：程序开始前，整个优先队列符合最大堆的结构，因此题中三个循环不变量都符合题意。在while循环开始前，A[i].key增大了，有可能会超过A[PARENT(i)].key，循环不变量c依旧满足。

保持：假设在值为\(i\)的循环执行之前\(3\)个循环不变量仍然保持。令pi = PARENT(i), ppi = PARENT(pi)。交换了节点i和pi后，根据循环不练量a, b，那么新节点i'满足A[i'] >= A[LEFT(i)].key, A[i'] >= A[RIGHT(i)].key。交换后节点i'保持了最大堆性质。新节点pi'的值相比pi时增大，因此可能发生A[ppi'].key < A[pi'].key的情况，循环不变量c对于pi'仍然成立；在交换之前，根据最大堆性质，A[ppi].key >= A[pi].key, A[ppi].key >= A[i xor 1].key成立。交换后，那么有A[ppi].key >= A[LEFT(pi')].key, A[ppi].key >= A[RIGHT(pi')].key成立，由此循环不变量a, b保持成立。

终止：最终，循环不变量c中所指出的最多一次冲突将不会存在，此时已经维护好整个最大堆。

6.5-8

1
2
3
4
5
6
7
8
9
10
11
12
MAX-HEAP-INCREASE-KEY(A, x, k)
  if k < x.key
    error “new key is smaller than current key”
  x.key = k
  find the index i in array A where object x occurs
  tmp = A[i]
  while i > 1 and A[PARENT(i)].key < tmp.key
    A[i] = A[PARENT(i)]
    updating the information that maps priority queue objects to array indices
    i = PARENT(i)
  A[i] = tmp
  updating the information that maps priority queue objects to array indices

6.5-9

我们将假设队列Q，栈S都有一个属性H，表示内置的最大优先队列，还有一个属性stamp，表示当前入栈/入队时应赋予的优先级。问题本质上是插入的元素按照单调递增还是单调递减的方式来赋予优先级。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 这里的N是指栈/队列默认的最大容量

ENQUEUE(Q, x)
  x.key = Q.stamp
  MAX-HEAP-INSERT(Q.H, x, N)
  Q.stamp = Q.stamp - 1

DEQUEUE(Q)
  x = MAX-HEAP-EXTRACT-MAX(Q.H)
  return x

PUSH(S, x)
  x.key = Q.stamp
  MAX-HEAP-INSERT(S.H, x, N)
  Q.stamp = Q.stamp + 1

POP(Q)
  x = MAX-HEAP-EXTRACT-MAX(Q.H)
  return x

6.5-10

1
2
3
4
5
6
MAX-HEAP-DELETE(A, x)
  find the index i in array A where object x occurs
  A[i] = A[A.heap-size]
  A.heap-size = A.heap-size - 1
  updating the information that maps priority queue objects to array indices
  MAX-HEAPIFY(A, i)

可以发现这个伪代码仅有第1行和第4行涉及索引表上的操作，第5行则用于维护最大堆的性质，时间复杂度为\(O(\lg n)\)。因此整体时间复杂度为\(O(\lg n)\)。

6.5-11

需要注意一些细节：

  • \(A[1 : k]\)是由\(k\)个长度不一的已排序数组组成，其中第\(i\)个数组的长度表示为A[i].size()。并且下标都是从\(1\)开始。
  • 本处使用最小堆的节点中，除了key以外，还有两个卫星数据r, c分别表示key是来自第r个数组的第c个元素。

第10行的while循环的执行次数恰好为\(n\)，因为每一次迭代最小堆弹出了这\(n\)个元素中的一个。并且，最小堆最大时的大小只有\(k\)，因此整个算法的时间复杂度为\(O(n\lg k)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
MERGE-K-SORTED-LISTS(A, k)
  Let H be new min-heap
  Let B be new array
  // n是全部序列长度总和。
  n = 0
  for i = 1 to k
    n = n + A[i].size()
  for i = 1 to k
    // 堆上的节点x的属性结构是(r, c, key)
    MIN-HEAP-INSERT(H, (i, 1, A[i, 1]), n)
  while H.heap-size() > 0
    r, c, key = MIN-HEAP-EXTRACT-MIN(H)
    INSERT(B, key)
    if c + 1 <= A[r].size()
      MIN-HEAP-INSERT(H, (r, c + 1, A[r, c + 1]), n)
  return B