6-3 Young氏矩阵
最后更新于：2022-04-01 07:35:12
#### 一、题目
#### 二、思考
最小Young氏矩阵和最小堆的思想差不多，可以通过比较两者的同异来理解Young氏矩阵
<!-- more -->
##### 不同点：
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[i*2]和H[i*2+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
```
#### 四、代码
[头文件](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/include/chapter6/Young.h)
[产品代码](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter6/Young.cpp)