> 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)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://windmising.gitbook.io/introduction-to-algorithms/introduction/thinking/6-3-young.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.