算法导论6.2 Exercises 答案

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

6.2-1

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

\(\begin{aligned} \langle 27,17,\underline{3},16,13,10,1,5,7,12,4,8,9,0\rangle\\ \langle 27,17,\underline{10},16,13,\underline{3},1,5,7,12,4,8,9,0\rangle\\ \langle 27,17,10,16,13,\underline{9},1,5,7,12,4,8,\underline{3},0\rangle \end{aligned}\)

6.2-2

根据堆在同一层上，从左到右铺满节点的特点，可以发现，根的左子树节点数一定不会低于根的右子树节点数，因此仅需要考虑根的左子树节点数。

而当这个堆是半满（也就是说在这一层中，根的左子树已经铺满所有节点，根的右子树没有任何一个节点）的时候，根的左子树节点数比重将达到最大。此时根的左子树可以视为是高度为\(h+1\)的满二叉树，有\(2^{h+1}-1\)个节点；根的右子树可以视为是高度为\(h\)的满二叉树，有\(2^{h}-1\)个节点；整个堆一共有\(2^{h+1}-1+2^h-1+1=3\cdot 2^h-1\)个节点。那么考虑左子树占整个堆的比重，有：

\(\dfrac{2^{h+1}-1}{3\cdot 2^h-1}=\dfrac{2\cdot 2^h-1}{3\cdot 2^h-1}<\dfrac{2\cdot 2^h}{3\cdot 2^h}=\dfrac{2}{3}\)

因此左子树占整个堆的比重至多为\(\dfrac{2}{3}\)，即至多\(\dfrac{2n}{3}\)的节点。

当这个堆是一个满二叉树时，根的左子树节点数比重将达到最小，因此\(\alpha=\dfrac{1}{2}\)。

因此，\(\alpha\)仍为\(\dfrac{2}{3}\)，对递推式没有什么影响，因为堆的子树最坏情况也只能是半满。

6.2-3

1
2
3
4
5
6
7
8
9
10
11
MIN-HEAPIFY(A, i)
  l = LEFT(i)
  r = RIGHT(i)
  if l <= A.heap-size and A[l] < A[i]
    smallest = l
  else smallest = i
  if r <= A.heap-size and A[r] < A[smallest]
    smallest = r
  if smallest != i
    exchange A[i] with A[smallest]
    MAX-HEAPIFY(A, smallest)

运行时间和算法MAX-HEAPIFY相同，都为\(O(\lg n)\)。

6.2-4

没有任何变化，因为节点\(i\)和其子节点已经满足了最大堆的性质。

6.2-5

没有任何变化，因为按照题目6.1-8的结论，此时\(i\)是叶子节点。

6.2-6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
MAX-HEAPIFY-NONRECURSIVE(A, i)
  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]
      i = largest
    else
      break

6.2-7

调用MAX-HEAPIFY(A, 1)，也就是让根节点的值下降。那么当这个节点的值下降到最深的一排的叶节点时，才能达到最坏情况。由于\(n\)个节点的堆的高度为\(\lfloor\lg n\rfloor\)，因此最坏情况下的时间复杂度为\(\Omega(\lg n)\)。