Young Tableau

A Young Tableau is a 2-D matrix in which each row is sorted left to right and each column is sorted top down. It has many nice properties. Young Tableau is discussed in the CLRS book.

The problem of searching for an item in the Young Tableau has 3 solutions here. The following are taken from this weblog.

In summary, to search a number x, the 3 strategies are:

1) A grid search: It is easy to see that element A[i][i] divides the matrix to 4 quadrants. if x < A[i][i], then we can remove the lower right sub-matrix, and search in the other 3 quadrants recursively. Cost is T(N)=3*T(N/4)+O(1), which is O(N^(log3/log4)), less than O(N).

2) Move along the matrix diagonal to find i, s.t. A[i][i] < k and A[i+1][i+1] > k. Now we have only 2 search intervals to search for. Cost is T(N)=2*T(N/4)+O(1), O(N). (? check again on this)

3) The most simple to implement strategy: "Start from the point in the last row first column. Every point to its right is greater than this point and every point on its top is smaller than this. So, if the point is greater than this point then move right otherwise move top. So, you will traverse at most 2*n points." Cost is O(N).

bool novice_search(int **grid,int size, int key,int &x,int &y)
{
  int i=size-1,j=0;
  while(0<=i && i<size && 0<=j && j<size) {
    if(grid[i][j]==key) {
      x=i;
      y=j;
      return true;
    } else if(grid[i][j] <key) {
      j++;
    } else {
      i--;
    }
  }
  return false;
}

[4/8/2010]

Major properties of a Young Tableau:

- Has properties similar to both Heap and BST.
- Search: O(m+n)
- Insert: O(m+n)
- Find min: O(1)
- Remove min: O(m+n), this is to shift elements to become a Young Tableau again.
- Find the k-th smallest: O(k(m+n)), since k is in [1, n*m], this is O(n^3).
A research paper (2006) on this is here, the result was O((sqrt(m)*lg(m))*(n*lg(n))+ m*lg(n)).