杨氏矩阵（Young Tableau）全解析：EXTRACT-MIN、插入、排序与查找的 O(m+n) 实现 —

文档
教程
教育

【免费下载链接】CLRS

📚 Solutions to Introduction to Algorithms Third Edition

项目地址：https://gitcode.com/gh_mirrors/clr/CLRS

杨氏矩阵（Young tableau）是一种同时满足"行有序"与"列有序"的二维数据结构，可用 $\infty$ 哨兵表示空位。本文围绕 CLRS《算法导论》第 6 章堆排序（Heapsort）的 Problem 6-3，系统讲解杨氏矩阵的定义、空满判定、$O(m+n)$ 的EXTRACT-MIN与插入算法、基于它实现的 $O(n^3)$ 排序，以及 $O(m+n)$ 的成员查找算法，并结合本仓库（CLRS 题解仓库）中堆相关章节与优先队列章节的源码级对应，帮助读者掌握一类"二维堆"的完整设计思路与复杂度分析方法。

1. 数据结构定义：行、列双有序的矩阵

一个 $m \times n$ 的**杨氏矩阵（Young tableau）**是一个 $m \times n$ 的矩阵，它同时满足两个约束：

每一行的元素从左到右非降序排列（sorted order from left to right）；
每一列的元素从上到下非降序排列（sorted order from top to bottom）。

矩阵中的部分条目可以被设为 $\infty$，这些 $\infty$ 被视作"不存在的元素"。因此，一个杨氏矩阵最多可以容纳 $r \le mn$ 个有限数值，即矩阵中非 $\infty$ 的条目数量不超过 $m \times n$。

该定义正是 6-3.md 原题开篇给出的形式化描述。从数据结构视角看，杨氏矩阵是二叉堆在二维网格上的推广：二叉堆只约束"父节点 ≤ 子节点"的树状偏序关系，而杨氏矩阵把这种偏序关系展开成"右邻居 ≥ 当前元素、下邻居 ≥ 当前元素"的网格偏序。这种结构使得它天然支持高效的"取最小、插入、查找"操作，下文逐一展开。

2. 构造示例：在 4×4 矩阵中放入 9 个元素（Part a）

原题要求在一个 $4 \times 4$ 的杨氏矩阵中放置元素集合 ${9, 16, 3, 2, 4, 8, 5, 14, 12}$。原文档给出的一个合法排布如下：

$$ \begin{matrix} 2 & 3 & 12 & 14 \ 4 & 8 & 16 & \infty \ 5 & 9 & \infty & \infty \ \infty & \infty & \infty & \infty \end{matrix} $$

验证该矩阵的合法性：观察第 1 行 $2 \le 3 \le 12 \le 14$，第 1 列 $2 \le 4 \le 5 \le \infty$，第 2 列 $3 \le 8 \le 9 \le \infty$……每一行从左到右、每一列从上到下均非降序；9 个有限数恰好占据前两行与第三行的前两格，其余位置由 $\infty$ 填充。

这里值得注意两点工程细节：

元素个数与容量：集合中恰好有 9 个元素，满足 $r = 9 \le mn = 16$；
$\infty$ 的分布：有限元素"贴着左上角"聚集，$\infty$ 全部集中在右下角区域。这正是杨氏矩阵可行排布的普遍形态——由于行、列都有序，一旦某个位置为 $\infty$，它右方和下方的所有位置也必然为 $\infty$。

3. 空表与满表的判定（Part b）

原题要求论证两个判定条件：

判定 1：若 $Y[1,1] = \infty$，则矩阵为空。

论证思路如下：若左上角元素为 $\infty$，由"行从左到右非降序"可知第一行的所有元素都 $\ge Y[1,1] = \infty$，即第一行全为 $\infty$；又由"列从上到下非降序"，每一列的第一个元素（位于第一行）均为 $\infty$，则该列其余元素也都 $\ge \infty$，于是整个矩阵所有元素均为 $\infty$，矩阵为空。

判定 2：若 $Y[m,n] < \infty$，则矩阵已满（恰好包含 $mn$ 个元素）。

论证思路对称：若右下角元素小于 $\infty$，由"行有序"可知最后一行所有元素都 $\le Y[m,n] < \infty$，即最后一行全是有限值；再由"列有序"，每一列的最后一个元素（位于最后一行）都是有限值，该列上方所有元素都 $\le$ 这个有限值，也全是有限值。于是整个矩阵没有任何 $\infty$，即恰好装满 $mn$ 个元素。

这两个判定本质上利用了"$\infty$ 只在右下角聚集"这一性质，是后续EXTRACT-MIN与插入算法正确性的基础：取最小值前先确认非空，插入前先确认未满。

4. EXTRACT-MIN：用"二维下沉"实现 $O(m+n)$ 取最小（Part c）

4.1 核心思想：$Y[1,1]$ 就是全局最小

由于矩阵的每一行、每一列都非降序，左上角元素 $Y[1,1]$ 一定不大于第一行的任何元素（行有序），也不大于第一列的任何元素（列有序），因此它是整个矩阵的最小值。原文档对EXTRACT-MIN的算法描述正是：

保存并返回 $A[1,1]$；
用 $\infty$ 替换 $A[1,1]$（相当于"删除"该元素）；
此时杨氏矩阵性质被破坏，需要执行一个类似 $\text{MAX-HEAPIFY}$ 的恢复过程。

4.2 恢复过程：比较邻居并交换到最小者

原文档给出的恢复策略是：

将当前元素 $A[i,j]$ 与它的右邻居 $A[i,j+1]$和下邻居 $A[i+1,j]$进行比较；
若邻居中存在更小的元素，则与其中最小的那个交换；
交换后，$A[i,j]$ 的位置性质恢复，但问题缩小为 $A[i,j+1]$ 或 $A[i+1,j]$（被交换过去的元素可能再次违反性质）；
当 $A[i,j]$ 不大于它的两个邻居时终止。

这与二叉堆中的 $\text{MAX-HEAPIFY}$（见 6.2.md 的 MAX-HEAPIFY 相关习题与 MIN-HEAPIFY 伪代码）在思路上完全同构：都是"把被破坏的元素沿结构向正确方向下沉"。区别仅在于二叉堆中节点至多有 2 个子节点，而杨氏矩阵中一个格子至多有 2 个"后继邻居"（右、下）。参考仓库中 MIN-HEAPIFY 的伪代码风格，可将杨氏矩阵的EXTRACT-MIN写成如下伪代码：

// 前置条件：Y 是非空 m×n 杨氏矩阵 // 令 T = m + n，运行时间为 O(T) = O(m + n) YOUNG-EXTRACT-MIN(Y, m, n) min = Y[1, 1] Y[1, 1] = ∞ i = 1 j = 1 while i < m or j < n // 在 (i, j+1) 与 (i+1, j) 中选出更小者 if j < n and (i == m or Y[i, j + 1] < Y[i + 1, j]) next_i = i next_j = j + 1 else if i < m next_i = i + 1 next_j = j else break // 已是右下角，无处可换 if Y[next_i, next_j] < Y[i, j] exchange Y[i, j] with Y[next_i, next_j] i = next_i j = next_j else break // 两个邻居都不比当前元素小，恢复完毕 return min

4.3 复杂度：递推式 $T(p) = T(p-1) + O(1)$

原题要求定义 $T(p)$（其中 $p = m + n$）为任意 $m \times n$ 杨氏矩阵上EXTRACT-MIN的最大运行时间，并给出递推关系。原文档给出的递推式为：

$$ T(p) = T(p - 1) + O(1) = T(p - 2) + O(1) + O(1) = \cdots = O(p). $$

推导逻辑：每次递归调用都把问题规模从 $m \times n$ 缩减为 $(m-1) \times n$ 或 $m \times (n-1)$，因此 $p = m + n$ 每次恰好减小 1，而每次递归内部的比较与交换都是常数时间 $O(1)$。展开后：

$$ T(p) = T(2) + (p - 2) \cdot O(1) = O(p) = O(m + n). $$

（当 $p = 2$ 即 $1 \times 1$ 矩阵时递归终止。）这与二叉堆HEAP-EXTRACT-MIN（6.5.md 中的伪代码）"取下堆顶 → 用末尾元素顶替 → 下沉修复"的流程相对应，只是堆的下沉路径长度是 $O(\lg n)$，而杨氏矩阵的下沉路径最多穿过 $m + n$ 个格子，故为 $O(m + n)$。对 $m = n$ 的方形矩阵，EXTRACT-MIN的代价为 $O(n)$。

5. 插入新元素：从右下角"上浮"（Part d）

插入算法与EXTRACT-MIN完全对称，原文档的描述是：从矩阵的右下角元素开始，把新元素向左上方移动到正确位置。

具体做法：

新元素初始放在 $Y[m,n]$（前提：矩阵未满，即 $Y[m,n] = \infty$，否则需要先"腾出"空间）；
将 $Y[i,j]$ 与它的左邻居 $Y[i,j-1]$和上邻居 $Y[i-1,j]$比较；
若邻居中存在更大的元素，则与其中更大的那个交换（保证新元素"上浮/左移"后仍保持行列有序）；
重复直到 $Y[i,j]$ 不小于它的左、上邻居（即它已到达正确位置）。

复杂度分析完全对称：每次比较交换是 $O(1)$，位置沿 $p = m + n$ 的递减方向移动，递推式同样是 $T(p) = T(p - 1) + O(1) = O(m + n)$。

这与二叉堆中的MIN-HEAP-INSERT（6.5.md 中的伪代码）——"在堆尾追加 $\infty$ 后再通过HEAP-DECREASE-KEY逐层上浮"——思路一致：都是先在结构末端放哨兵，再把新值沿父/祖先方向调整到合适位置。伪代码如下：

// 前置条件：Y 是未满的 m×n 杨氏矩阵（Y[m,n] = ∞） YOUNG-INSERT(Y, m, n, key) if Y[m, n] != ∞ error "tableau overflow" i = m j = n Y[i, j] = key while i > 1 or j > 1 // 在 (i-1, j) 与 (i, j-1) 中选出更大者 if i > 1 and (j == 1 or Y[i - 1, j] > Y[i, j - 1]) prev_i = i - 1 prev_j = j else if j > 1 prev_i = i prev_j = j - 1 else break // 已到左上角 if Y[prev_i, prev_j] > Y[i, j] exchange Y[i, j] with Y[prev_i, prev_j] i = prev_i j = prev_j else break // 左、上邻居都不比当前元素大，位置正确 return

6. 用 $n \times n$ 杨氏矩阵排序 $n^2$ 个数：$O(n^3)$（Part e）

6.1 经典做法：空表 + 依次插入 + 依次取最小

原题要求不借助任何其他排序方法作为子程序，仅用 $n \times n$ 杨氏矩阵对 $n^2$ 个数排序。原文档给出的方案：

从一个空杨氏矩阵开始，把 $n^2$ 个元素依次插入（每次调用YOUNG-INSERT）；
插入完成后，依次执行YOUNG-EXTRACT-MIN，把取出的元素按序写回原数组，得到升序结果。

复杂度核算：

每次插入：$O(n + n) = O(n)$（因为 $m = n$，$p = 2n$）；
$n^2$ 次插入：$n^2 \cdot O(n) = O(n^3)$；
每次提取：$O(n)$；$n^2$ 次提取：同样 $O(n^3)$；
总计：$O(n^3)$，与原题要求的界一致。

从原题的角度，这个 $O(n^3)$ 的排序算法还揭示了一个有趣的复杂度对比：二叉堆排序是 $O(n\lg n)$，而用杨氏矩阵排序是 $O(n^3)$，两者都基于"插入 + 取最小"的优先队列范式，代价差异完全来自单次操作的成本（堆每次 $O(\lg n)$，杨氏矩阵每次 $O(n)$）。这正是 6.5.md 中优先队列抽象（HEAP-EXTRACT-MIN、MIN-HEAP-INSERT）在另一种底层数据结构上的移植。

6.2 原地变体：部分杨氏矩阵与常数空间

原文档还给出了一个更精巧的**原地（in-place）**改进方案：

允许"部分"杨氏矩阵——即只有前若干行（以及其中最后一行的一部分）参与构成矩阵；
直接在原数组上构建杨氏矩阵，构建完成后，把每次取出的最小元素放到数组末尾；
这种做法的渐近复杂度不变（仍为 $O(n^3)$），但只使用常数辅助内存；
一个附带效果是：这样得到的结果是**逆序（降序）**排列。

原地变体的意义在于证明杨氏矩阵不只是一个理论玩具：它可以在 $O(n^3)$ 时间内以常数额外空间完成排序，这在内存受限场景中是有实际价值的权衡。

7. 成员查找：从左下角出发的 $O(m+n)$ 搜索（Part f）

原题要求设计 $O(m+n)$ 时间算法判断给定数是否存在于 $m \times n$ 杨氏矩阵中。原文档给出的策略是从矩阵左下角开始：

设当前元素为current，待查找数值为key；
若current > key：向上移动（当前元素所在列的更上方元素更小）；
若current < key：向右移动（当前元素所在行的更右方元素更大）；
若current = key：查找成功；
若走出矩阵边界：查找失败。

伪代码：

// 从 (m, 1) 出发，O(m + n) 时间 YOUNG-SEARCH(Y, m, n, key) i = m j = 1 while i >= 1 and j <= n if Y[i, j] == key return true else if Y[i, j] > key i = i - 1 // 向上：更小 else j = j + 1 // 向右：更大 return false

为什么起点选左下角？这是该算法的关键：左下角 $Y[m,1]$ 是"行方向最小、列方向最大"的边界位置，从它出发，两个方向上的移动方向完全确定——current > key时只能向上（同一行向右只会更大，向上才会变小），current < key时只能向右（同一列向上只会更小，向右才会变大）。每一步都严格排除一行或一列的搜索范围，因此最多移动 $m + n$ 次，达到 $O(m+n)$。注意：若从左上角出发，两个方向都存在更小值，方向不确定，无法保证线性时间。

这个"从对角边界出发、沿单调方向收缩搜索空间"的技巧与第 9 章"选择与顺序统计量"、二维 Monge 数组等问题的处理手法一脉相承，值得单独掌握。

8. 复杂度总览与延伸思考

8.1 操作复杂度汇总

操作	时间复杂度	关键位置/思路	对应仓库章节
`EXTRACT-MIN`	$O(m+n)$	从 $Y[1,1]$ 取最小值，沿右/下方向下沉	6.5.md HEAP-EXTRACT-MIN、6.2.md MIN-HEAPIFY
`INSERT`	$O(m+n)$	从 $Y[m,n]$ 放入新值，沿左/上方向上浮	6.5.md MIN-HEAP-INSERT
排序 $n^2$ 个数（$n\times n$ 矩阵）	$O(n^3)$	空表依次插入 + 依次取最小，可原地	6-3.md Part e
成员查找	$O(m+n)$	从左下角出发，向上/向右单调移动	6-3.md Part f

8.2 与堆家族的关系

从仓库中 Problem 6-2（d-ary heap）可以看到堆家族的扩展思路：二叉堆（$d = 2$）可推广为 $d$ 叉堆，其EXTRACT-MAX的代价为 $O(d\log_d n)$；而杨氏矩阵可以理解为把"扇出系数 $d$"进一步推广成"二维网格"的结构，代价函数也从 $O(\lg n)$ 变为 $O(m + n)$。三者的共性在于：