#### 一、題目  #### 二、思考 最小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)