from: http://blog.csdn.net/michealmeng555/archive/2008/05/28/2489923.aspx
杨氏矩阵 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 |
10 |
21 |
23 |
33 |
56 |
∞ |
c |
34 |
37 |
45 |
55 |
∞ |
∞ |
d |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
e |
图1-3
由操作知,删除算法时间复杂同样最多为行列之和,即O(m + n)
。
【3
】查找算法
查找算法类似于BST
二叉排序树,不过需要在其思想上稍微进行修改,才能满足杨氏矩阵的查找操作,同样利用杨氏矩阵的性质,不过此时应该换一个角度思考问题,因为与BST
二叉排序树类比,所以应该从左下角
开始看起(如
图1-1
d1
位置),该元素的上面的元素比本身小和右面的元素比本身大,这样就与BST
二叉排序树具有相同的性质。所以在查找时从左下角不断的比较,从而最终确定所查找元素位置。
如查找19
,
比较顺序如
图1-4
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
3 |
5 |
7 |
8 |
11 |
a |
4 |
|
|
|
|
19 |
b |
|
21 |
23 |
33 |
56 |
57 |
c |
34 |
37 |
45 |
55 |
∞ |
∞ |
d |
∞ |
∞ |
∞ |
|