Question

6-1 用插入方法建堆

```c++
void Heap::Build_Max_Heap()
{
heap_size = 1;
//从堆中最后一个元素开始，依次调整每个结点，使符合堆的性质
for(int i = 2; i <= length; i++)
Max_Heap_Insert(A[i]);
}

答：

a）A = {1,2,3};

b）MAX-HEAP-INSERT 的过程如下：

加入大小为-0x7FFFFFFF 的新结点，O(1)

将该值调整为 key,最坏情况下为 O(lgn)

对每个结点都要执行一次插入操作，因此最坏时间为 O(nlgn)

### 6-2 对 d 叉堆的分析

a）根结点是 A[1]，根结点的孩子是 A[2],A[3],……，A[d+1]

PARENT(i) = (i - 2 ) / d + 1  

CHILD(i, j ) = d * (i - 1) + j + 1  

b）lgn/lgd  

c）HEAP-EXTRACR-MAX(A) 与二叉堆的实现相同，其调用的 MAX-HEAPIFY(A, i) 要做部分更改，时间复杂度是 O(lgn/lgd * d)  

MAX-HEAPIFY(A, i)
1 largest <- i
2 for j <- 1 to d
3 k <- CHILD(i, j)
4 if k <= heap-size[A] and A[k] > A[largest]
5 largest <- k
6 if largest != i
7 then exchange A[i] <-> A[largest]
8 MAX-HEAPIFY(A, largest)

d）和二叉堆的实现完全一样，时间复杂度是 O(lgn/lgd)  

e）和二叉堆的实现完全一样，时间复杂度是 O(lgn/lgd) 

### 6-3 Young 氏矩阵

见[算法导论 6-3 Young 氏矩阵](6-3 Young 氏矩阵.md)

一、题目

二、思考

最小 Young 氏矩阵和最小堆的思想差不多，可以通过比较两者的同异来理解 Young 氏矩阵

不同点：

header 1	min-Heap	min-Young
堆顶（最小值）	H[1]	Y[i][j]
最后一个元素的位置	H[N]	Y[N][N]
最后一个元素	不一定是最大值	一定是最大值
parent	H[i]的 parent 是 H[i/2]	Y[i][j]的 parent 是 Y[i-1][j]和 Y[i][j-1]
child	H[i]的 child 是 H[i2]和 H[i2+1]	Y[i][j]的 child 是 Y[i+1][j]和 Y[i][j+1]
find(x)	从 H[1]开始遍历	从西南角开始，或当前值小于 key，则向东走，否则向北走

相同点：

1.堆顶是最小值所在的位置

2.parent 的值<=child 的值

3.空条件：堆顶元素值为 INIT

4.满条件：最后一个元素的值不为 INIT

5.delete：插入到最后一个元素的位置，然后向 parent 调整

6.extract：提取堆顶元素，将堆顶元素置为 INIT，然后 child 调整

三、练习

a）

可以有多种画法

2   3   4   5  
8   9   12  
14  16  

c）

提取 Y[1][1]，并用 ox7FFFFFFF 填充。然后向右下调整

YOUNG-EXTRACR-MIN(Y)  
1  if  Y[1][1] == 0X7FFFFFFF  
2    then error "heap underflow"  
3  min <- Y[1][1]  
4  A[1][1] <- 0X7FFFFFFF  
5  MAX-HEAPIFY(Y, 1, 1)  
6  return min  
//递归  
MIN-YOUNGIFY(Y, i, j)  
 1  min <- Y[i][j]  
 2  mini <- i  
 3  minj <- j  
 4  if i+1 < m and Y[i+1][j] < min  
 5    mini <- i+1  
 6    minj <- j  
 7    min <- Y[i+1][j]  
 8  if j+1 < n and Y[i][j+1] < min  
 9    mini <- i  
10    minj <- j+1  
11    min <- Y[i][j+1]  
12  if i != mini or j != minj  
13    exchange Y[i][j] <-> Y[mini][minj]  
14    MIN-YOUNGIFY(Y, mini, minj)  
d）  
//若表未满，插入到右下角，然后向左上调整  
MIN-YOUNG-INSERT(Y, key)  
 1  if Y[m][n] < 0x7fffffff  
 2    then error "young overflow"  
 3  Y[m][n] <- key  
 4  flag <-  true  
 5  i <- m  
 6  j <- n  
 7  max <- key  
 8  maxi <- i  
 9  maxj <- j  
10  while true  
11    if i > 1 and max < Y[i-1][j]  
12      maxi <- i - 1  
13      maxj <- j  
14      max <- Y[i-1][j]  
15    if j > 1 and max < Y[i][j-1]  
16      maxi <- i  
17      maxj <- j-1  
18      max <- Y[i][j-1]  
19    if max == Y[i][j]  
20      break  
21    exchange Y[maxi][maxj] <-> Y[i][j]  
22    i <- maxi  
23    j <- maxj  
24    max <- Y[i][j]  

d)

将新元素加入到矩阵的 Y[m][n]处，然后逐步向上调整

参考产品代码 errorType Young::insert(int key)

e）

排序过程为：

step1:取下矩阵 Y[1][1]元素，O(1)

step2:将 Y[1][1]置为 0x7FFFFFFF，O(1)

step3:调整矩阵，O(n)

对所有 n^2^个结点各执行以上 step1~3 一次，因此时间为 O(n^3^)

f）

从左下角开找，若比它小，则向上，则比它大，则向右找

FIND-YOUNG-KEY(Y, key)  
 1  i <- m  
 2   j <- 0  
 3   while i >= 1 and j <= n  
 4     if Y[i][j] = key  
 5     then return true  
 6     else if Y[i][j] < key  
 7     then j++  
 8     else if Y[i][j] > key  
 9     then i--  
10   return false  

四、代码

头文件

产品代码