Question

6.1 堆

6.1-1

最多 2^(h+1) - 1， 最少 2 ^ h（当树中只有一个结点时，高度是 0）

6.1-2

上一题结论 ==> 2^h <= n <= 2^(h+1) - 1

     ==> h <= lgn <= h + 1

     ==> lgn = h

6.1-3

max-heap 的定义
==>A[PARENT(i)]>=A[i]
==>A[1]>A[2],A[3]
==>A[1]>A[4],A[5],A[6],A[7]
==>……
==>the root of the subtree contains the largest value

6.1-4

叶子上

6.1-5

是最小堆或最大堆

6.1-6

不是，7 是 6 的左孩子，但 7>6

6.1-7

A[2i]、A[2i+1]是 A[i]的孩子
==>若 2i<=n&&2i+1<=n，则 A[i]有孩子
==>若 2i>n，则 A[i]是叶子
==>the leaves are the nodes indexed by ?n/2 ? + 1, ?n/2 ? + 2, . . . , n

6.2 保持堆的性质

6.2-1

A = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}

A = {27,17,10,16,13,3,1,5,7,12,4,8,9,0}

A = {27,17,10,16,13,9,1,5,7,12,4,8,3,0}

6.2-2

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

6.2-3

没有效果，程序终止

6.2-4

i > heap-size[A]/2 时，是叶子结点，也没有效果，程序终止

6.2-5

我还是比较喜欢用 C++，不喜欢用伪代码

```c++
void Heap::Max_Heapify(int i)
{
int l = (LEFT(i)), r = (RIGHT(i)), largest;
//选择 i、i 的左、i 的右三个结点中值最大的结点
if(l <= heap_size && A[l] > A[i])
largest = l;
else largest = i;
if(r <= heap_size && A[r] > A[largest])
largest = r;
//如果根最大，已经满足堆的条件，函数停止
//否则
while(largest != i)
{
//根与值最大的结点交互
swap(A[i], A[largest]);
//交换可能破坏子树的堆，重新调整子树
i = largest;
l = (LEFT(i)), r = (RIGHT(i));
//选择 i、i 的左、i 的右三个结点中值最大的结点
if(l <= heap_size && A[l] > A[i])
largest = l;
else largest = i;
if(r <= heap_size && A[r] > A[largest])
largest = r;
}
}

##### 6.2-6

MAX-HEAPIFY 中每循环一次，当前处理的结点的高度就会+1，最坏情况下，结点是根结点的时候停止，此时结点高度是 logn，因此最坏运行时间是 logn

### 6.3 建堆

##### 6.3-1

A = {5,3,17,10,84,19,6,22,9}
A = {5,3,17,22,84,19,6,10,9}
A = {5,3,19,22,84,17,6,10,9}
A = {5,84,19,22,3,17,6,10,9}
A = {84,5,19,22,3,17,6,10,9}
A = {84,22,19,5,3,17,6,10,9}
A = {84,22,19,10,3,17,6,5,9}

##### 6.3-2

因为 MAX-HEAPIFY 中使用条件是当前结点的左孩子和右孩子都是堆

假设对 i 执行 MAX-HEAPIFY 操作，当 i=j 时循环停止，结果是从 i 到 j 的这条路径上的点满足最大堆的性质，但是 PARENT[i]不一定满足。

甚至有可能在满足 A[PARENT(i)]>A[i]的情况下因为执行了 MAX-HEAPIFY(i) 而导致 A[PARENT(i)]<A[i]，例如下图，

因此一定要先执行 MAX-HEAPIFY(i) 才能执行 MAX-HEAPIFY(PARENT(i))

![](http://box.kancloud.cn/2016-02-02_56b02bd032fb2.jpg)

##### 6.3-3

对于一个含有 n 个结点的堆，最多可以有 f(h) 个叶子结点

已知，当 h=0 时，f(h)=(n+1)/2

高度为 h 的结点是高度为 h-1 的结点的父结点，因此 f(h) = (f(h-1) + 1) / 2

f(0) = (n + 1) / 2 = 1 + (n-1)/2
f(1) = (f(0) +1) / 2 = 1 + (n-1)/(2^2)
f(2) = (f(1) +1) / 2 = 1 + (n-1)/(2^3)
……
f(h) = 1 + (n-1) / (2 ^ (h+1))

因为 f(h) 必须是整数，所以

f(h) = floor[1 + (n-1) / (2 ^ (h+1)) ]
= ceilling[(n-1) / (2 ^ (h+1))]
≤ ceilling[n / (2 ^ (h+1))]

得证：在任一含 n 个元素的堆中，至多有 ceiling(n/(2^(h+1))) 个高度为 h 的节点。

参考 http://blog.csdn.net/lqh604/article/details/7381893

### 6.4 堆排序的算法

##### 6.4-1

A = {5,13,2,25,7,17,20,8,4}

A = {25,13,20,8,7,17,2,5,4}

A = {4,13,20,8,7,17,2,5,25}

A = {20,13,17,8,7,4,2,5,25}

A = {5,13,17,8,7,4,2,20,25}

A = {17,13,5,8,7,4,2,20,25}

A = {2,13,5,8,7,4,17,20,25}

A = {13,8,5,2,7,4,17,20,25}

A = {4,8,5,2,7,13,17,20,25}

A = {8,7,5,2,4,13,17,20,25}

A = {4,7,5,2,8,13,17,20,25}

A = {7,4,5,2,8,13,17,20,25}

A = {2,4,5,7,8,13,17,20,25}

A = {5,4,2,7,8,13,17,20,25}

A = {2,4,5,7,8,13,17,20,25}

A = {4,2,5,7,8,13,17,20,25}

A = {2,4,5,7,8,13,17,20,25}

A = {2,4,5,7,8,13,17,20,25}

##### 6.4-2

初始化：第一轮迭代之前，i=length[A]，则 i=n。显然，循环不变式成立。

保持：每次迭代前，对于一个给定的 i。假设循环不变式成立，则子数组 A[1..i]是一个包含了 A[1..n]中的 i 个最小元素的最大堆；而子数组 A[i+1..n]包含了已排序的 A[1..n]中的 n-i 个最大元素。经过 3~5 行代码的操作后，使得子数组 A[1..i-1]是一个包含了 A[1..n]中的 i-1 个最小元素的最大堆；子数组 A[i..n]包含了已排序的 A[1..n]中的 n-i+1 个最大元素。则可以保证 i=i-1 后的下一次迭代开始前，循环不变式成立。

终止：循环终止时，i=1。根据循环不变式，子数组 A[i+1..n]即 A[2..n]包含了已排序的 A[1..n]中的 n-1 个最大元素，所以数组 A 是已排好序的。

##### 6.4-3

按递增排序的数组，运行时间是 nlgn

按递减排序的数组，运行时间是 n

#####6.4-4

堆排序算法中，对堆中每个结点的处理过程为：

（1）取下头结点，O(1)

（2）把最后一个结点移到根结点位置，O(1)

（3）对该结点执行 MAX-HEAPIFY，最坏时间为 O(lgn)

对每个结点处理的最坏时间是 O(lgn)，每个结点最多处理一次。

因此最坏运行时间是 O(nlgn)

### 6.5 优先级队列

##### 6.5-1

A = {15,13,9,5,12,8,7,4,0,6,2,1}

A = {1,13,9,5,12,8,7,4,0,6,2,1}

A = {13,1,9,5,12,8,7,4,0,6,2,1}

A = {13,12,9,5,1,8,7,4,0,6,2,1}

A = {13,12,9,5,6,8,7,4,0,1,2,1}

return 15

##### 6.5-2

A = {15,13,9,5,12,8,7,4,0,6,2,1}

A = {15,13,9,5,12,8,7,4,0,6,2,1,-2147483647}

A = {15,13,9,5,12,8,7,4,0,6,2,1,10}

A = {15,13,9,5,12,10,7,4,0,6,2,1,8}

A = {15,13,10,5,12,9,7,4,0,6,2,1,8}

##### 6.5-3

HEAP-MINIMUM(A)
1 return A[1]
HEAP-EXTRACR-MIN(A)
1 if heap-size[A] < 1
2 then error "heap underflow"
3 min <- A[1]
4 A[1] <- A[heap-size[A]]
5 heap-size[A] <- heap-size[A] - 1
6 MIN-HEAPIFY(A, 1)
7 return min
HEAP-DECREASE-KEY(A, i, key)
1 if key > A[i]
2 then error "new key is smaller than current key"
3 A[i] <- key
4 while i > 1 and A[PARENT(i)] > A[i]
5 do exchange A[i] <-> A[PARENT(i)]
6 i <- PARENT(i)
MIN-HEAP-INSERT
1 heap-size[A] <- heap-size[A] + 1
2 A[heap-size[A]] <- 0x7fffffff
3 HEAP-INCREASE-KEY(A, heap-size[A], key)

##### 6.5-4

要想插入成功，key 必须大于这个初值。key 可能是任意数，因此初值必须是无限小

#####6.5-6

FIFO：以进入队列的时间作为权值建立最小堆

栈：以进入栈的时间作为权值建立最大堆

#####6.5-7

```c++
void Heap::Heap_Delete(int i)
{
  if(i > heap_size)
  {
    cout<<"there's no node i"<<endl;
    exit(0);
  }
  int key = A[heap_size];
  heap_size--;
  if(key > A[i])   //最后一个结点不一定比中间的结点最
    Heap_Increase_Key(i, key);
  else
  {
    A[i] = key;
    Max_Heapify(i);
  }
}

6.5-8

step1：取每个链表的第一个元素，构造成一个含有 k 个元素的堆

step2：把根结点的值记入排序结果中。

step3：判断根结点所在的链表，若该链表为空，则 go to step4，否则 go to step5

step4：删除根结点，调整堆，go to step2

step5：把根结点替换为原根结点所在链表中的第一个元素，调整堆，go to step 2

产品代码

测试代码