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

    由上述的操作知其时间复杂度最大为行列之和，即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-3

  由操作知，删除算法时间复杂同样最多为行列之和，即O(m + n) 。

    【3 】查找算法

     查找算法类似于BST 二叉排序树，不过需要在其思想上稍微进行修改，才能满足杨氏矩阵的查找操作，同样利用杨氏矩阵的性质，不过此时应该换一个角度思考问题，因为与BST 二叉排序树类比，所以应该从左下角 开始看起（如 图1-1 d1 位置），该元素的上面的元素比本身小和右面的元素比本身大，这样就与BST 二叉排序树具有相同的性质。所以在查找时从左下角不断的比较，从而最终确定所查找元素位置。

    如查找19 ， 比较顺序如 图1-4

 

图1-4

  此算法的时间复杂度同前两个算法，复杂度也是O(m + n) 。

总结：

     经 过这次对杨氏矩阵的研究，感觉书本上学到的数据结构只是一些最基本的东西，其实在生活中有很多复杂，并且有趣的数据结构模型，但是这些数据结构模型最终将 可以用已有的简单数据结构来经过变换，以及组合来构成，同时相应的算法也就有所扩展。所以我认为在学习的过程中应该注重对一些问题的深入研究。

附c++ 源码

注：本源代码仅实现了插入功能，并且在vc++6.0 编译通过，程序仅对简单的数据测试通过，可能存在bug ，在此写出简单的源码重在说明杨氏矩阵的算法思想。

#include "iostream.h"

 

#define MAX1 5

#define MAX2 6

#define INF 99999

 

void Insert( int x, int *young );

void Delete( int x, int y, int *young );

void Find( int x, int *young );

 

void main()

{

    int young[MAX1][MAX2]={1,3,5,7,8,11,4,6,9,14,15,19,10,21,23,33,56,57,34,37,45,55,INF,INF,INF,INF,INF,INF,INF,INF};

    int choice=0;

    int insert;

    int k,s;// 用于计数

    cout<<"young tableau 的插入功能"<<endl;

    cout<<"young tableau:"<<endl;

    for(int i=0; i<MAX1; i++)

       for(int j=0; j<MAX2; j++)

       {

           cout<<young[i][j]<<' ';

           if( j==MAX2-1 )

              cout<<endl;

       }

    cout<<endl<<" 请选择：1-3"<<endl;

    cout<<"1. 插入"<<endl;

    cout<<"2. 删除"<<endl;

    cout<<"3. 查找"<<endl;

    while( choice<1 || choice>3 )

       cin>>choice;

    switch(choice)

    {

       case 1:

           cout<<" 请输入要插入的数字:";

           cin>>insert;

           Insert(insert, *young); 

           cout<<"young tableau:"<<endl;

           for(k=0; k<MAX1; k++)

              for(s=0; s<MAX2; s++)

                  {

                     cout<<young[k][s]<<' ';

                     if( s==MAX2-1 )

                     cout<<endl;

                  }

           break;

       case 2:

           break;

       case 3:

           break;

    }

}

void Insert(int insert, int *young)

{

    int x=4;

    int y=5;// 为young 表中第一个无穷的位置，并且用来定位当前待比较交换的位置

    *(young+6*(x-1)+(y-1))=insert;

    for(int i=x+y;  ; i--)

    {

       int insert_l= *(young+6*(x-1)+(y-2));

       int insert_u= *(young+6*(x-2)+(y-1));

       if(x==1)

           insert_u=0;

       if(y==1)

           insert_l=0;

       if(insert<insert_l || insert<insert_u )

       {

           if( insert_l > insert_u )

           {

              int temp=insert_l;

              *(young+6*(x-1)+(y-2)) = *(young+6*(x-1)+(y-1));

              *(young+6*(x-1)+(y-1)) =temp;

              y--;

           }

           else

           {

              int temp=insert_u;

              *(young+6*(x-2)+(y-1)) = *(young+6*(x-1)+(y-1));

              *(young+6*(x-1)+(y-1)) =temp;

              x--;

           }

       }

       else break;

    }

}