算法导论思考题：6-3Young 矩阵

三.Young 氏矩阵的相关算法.

题:一个 m*n 的 Young 氏矩阵(Young tableau) 是一个 m*n 的矩阵,其中每一行的数据都从左到右排序,第一列的数据都从上到下排序.Young氏矩阵中可能会有一些∞ 数据项,表示不存在的元素.所以,Young 氏矩阵可以用来存放 r<= mn 个有限的元素.

a).画一个包含{9,16,3,2,4,8,5,14,12} 的4*4 的Young 氏矩阵.

b).给出一个在非空 m*n 的 Young 氏矩阵上实现 EXTRACT-MIN 算法,使其运行时间为O(m+n).

c).说明如何在O(m+n)时间内,将一个新元素手入到一个未满的 m*n Young 氏矩阵中.

d).给出一个时间复杂度为 O(n^3) 的对 n*n Young 氏矩阵排序的算法.

f).给出一个运行时间为O(m+n) 的算法,来决定一个给定的数是否存在于一个给定的 m*n的 Young 氏矩阵当中.

//题目文字引用自http://blog.csdn.net/atyuwen/archive/2007/10/15/1826233.aspx

解答：

b）算法一：EXTRACT-MIN 算法取出Y[0][0],然后调整Young矩阵，使得算法调整的是新的Young矩阵。必须从向右和向下的方向选取一个元素代替被选出的元素，所以，其调整过程有点像堆的maxheapify，一直调整到最后一个元素。

算法二：E（m1,m2,n1,n2）算法取出Y[m1][n1],然后面临的问题是我们要选择的是替代的哪一个呢，我们需要从Y[m1+1,n1]或者Y（m1,n1,）中选择小的，如果我们选择了Y[m1+1,n1]，接着需要进行E（m1+1,m2,n1,n2），我们选择了Y（m1,n1,）时需要进行E（m1+1,m2,n1,n2）。

c)在最后一个位置Y[m-1][n-1]插入x，此时需要比较x和左边和上边的元素。选择最大的数来放入x的位置，不停地向左向上，x元素的左边和上边的元素都小于x，或者到达了边界。

d）n*n的 EXTRACT-MIN 算法，每次抽出剩下的元素中最小的元素。

f)以行为单位，比较被查找的元素x是不是大于等于行首元素并且小于等于行尾元素，则