> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/introduction-to-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/introduction-to-algorithms/introduction/thinking/6-3-young.md). # 6-3 Young ## 一、题目 ![](http://windmissing.github.io/images_for_gitbook/Introduction_to_Algorithms/1.gif) ## 二、思考 最小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\[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)