6-3 Young

一、题目

二、思考

最小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

四、代码

头文件

产品代码