算法研讨的论文【原创分享】
杨氏矩阵 Young Tableau
前几天算法课上老师提到了一个数据结构--Young Tableau，只是简单的提了一下，没有仔细的讲解，于是自己在网上搜集了一些资料，并且加以研究，感觉杨氏矩阵（Young Tableau）是一个很奇妙的数据结构，他类似于堆的结构，又类似于BST的结构，对于查找某些元素，它优于堆；对于插入、删除它比BST更方便。
首先介绍一下这个数据结构的定义，Young Tableau有一个m*n的矩阵，让后有一数组 a[k], 其中 k<=m*n ，然后把a[k]中的数填入 m*n 的矩阵中，填充规则为（如图1-1）：
1. 每一行每一列都严格单调递增（有其他的版本是递减，其原理相同）。
2. 如果将a[k]中的数填完后，矩阵中仍有空间，则填入 ∞。
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
3 |
5 |
7 |
8 |
11 |
a |
|
4 |
6 |
9 |
14 |
15 |
19 |
b |
|
10 |
21 |
23 |
33 |
56 |
57 |
c |
|
34 |
37 |
45 |
55 |
∞ |
∞ |
d |
|
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
e |
图1-1
则现在讨论，这个数据结构的几种操作，而在这些操作中，我们会发现堆排序的影子，并且这些操作具有很好的时间复杂度。
条件：一个已经建好的杨氏矩阵（Young Tableau）
操作：
【1】 在杨氏矩阵中插入元素x ---- Insert(x)
【2】 在杨氏矩阵中删除位于 (x, y) 位置的元素---- Delete(x, y)
【3】 返回x是否在矩阵中----Find(x)
其中1-2操作类似于堆的操作，而4操作类似于BST的操作。下面我就用我
自己的理解把这几个操作加以解释。
【1】 插入操作
本操作的时间复杂度为O( n + m ),其操作类似于堆排序的SIFT-UP算法(具体算法见《算法设计技巧与分析》 M.H,Alsuwaiyel 著)。它的堆的结构在这里表现为某个元素Y[x, y] 下面和右面的两个元素 Y[x, y+1] ,Y[x+1, y]均比Y[x, y]要大。于是其插入算法可以描述为，首先把待插入元素以行为主序置于所有有效数字（除了无穷以外的数）最后面，如将x=2，放入 图1-1 的d5的位置，然后执行类似于SIFT-UP的操作，将x与它左边（记为x-l）及上面（记为x-u）的数进行比较，根据比较结果有三种可能的操作：
1：x-u > x 且x-u >= x-l 则将x 与 x-u进行交换
2：x-l > x 且x-l > x-u 则将x 与 x-l进行交换
3: x >= x-l 且 x > x-u 则x 不动，此时已经插入成功
（可以有其他合理的约定）
对例子插入2进行操作如图1-2箭头的操作方向。
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
3 |
5 |
7 |
8 |
11 |
a |
|
|
6 |
9 |
14 |
15 |
19 |
b |
|
|
|
|
|
|
57 |
c |
|
34 |
37 |
45 |
55 |
56 |
∞ |
d |
|
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
e |
图1-2
由上述的操作知其时间复杂度最大为行列之和，即O(m+n)。
【2】 删除操作
操作类似于插入操作，其时间复杂度也为O(m+n)。其操作类似于堆排序的SIFT-DOWN算法。删除算法可以描述为，首先将删除的位置(x, y)的数字删除，然后调整，把杨氏矩阵中的最大值k（可以行为主序进行搜索到最后）填入到被删除位置，然后让此数与其下面的数(k-d)和右面的数进行(k-r)比较,此时比较结果为两种，因为此时元素一定会下移：
1：k-d > k-r 将k-r 和 k进行交换
2：k-d < k-r 将k-d 和 k进行交换
举例 删除图1-1的a3位置的元素5如图1-3
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
3 |
7 |
|
|
|
a |
|
4 |
6 |
9 |
14 |
15 |
57 |
b |
|
|
