ALGORITHMS

Young Tableau

Young氏矩阵（Young tableau）：每一行从左到右排序，每一列从上到下排序。若某一元素为 \(\infty\)，则表示空。故一个Young氏矩阵可以保存 \(n \le M \times N\) 个有穷数。

Young氏矩阵性质

  • 对Young tableau中任意元素tableau[i, j],必有在以(i, j)为右下角的”子矩阵”中，tableau[i, j]最大。

    即在Young tableau中的非空元素部分，右下边界构成了整个矩阵的”最大值集”

  • 若 tableau[0, 0] = Inf ,则表为空表. 若tableau[m - 1, n - 1] != Inf 则表已满。
  • 各行, 各列有序

Young tableau类似于一个二叉堆，任意一结点由二元组 \((i,j)\) 标识，且其二”子结点”为 \((i−1,j)\)，\((i，j−1)\)。但与二叉堆不同的是，不同结点的子结点中可能存在重叠。如 \((i−1,j)\)，\((i，j−1)\) 有公共子结点 \((i−1,j−1)\) 。因此，可推知Young tableau拥有比二叉堆更强的”堆序性”。

Young tableau操作

上滤

如二叉堆一般，基本思想为寻找到结点 \((i,j)\) 及其两子结点 \((i−1,j) \ , \ (i,j−1)\) 的中最大值。若为其本身，则表明该部分已经有序且满足Young tableau的性质。

若不是，则交换其与最大值的位置，而后递归。此时即可知，为何要初始化Young tableau的空为 \(\infty\)。因为仅当”空穴”为 \(\infty\)，与”空穴”的交换才总是有意义且成立的。

注意到tableau为二维数组，需要单独判断上边界与左边界。

同时需知，该上滤操作能成功的基础为 除 \((i,j)\) 外，其他非空结点处的值有序，满足Young tableau的性质。

void  PercolateUp(ElementType tableau[][N], int i, int j) {
    // at the top border
    if (i == 0) {
        ElementType key = tableau[i][j];
        for (; j > 0 && key < tableau[i][j - 1]; j--) {
            tableau[i][j] = tableau[i][j - 1];
        }
        tableau[i][j] = key;

        return;
    }

    // at the left border
    if (j == 0) {
        ElementType key = tableau[i][j];
        for (; i > 0 && key < tableau[i - 1][j]; i--) {
            tableau[i][j] = tableau[i - 1][j];
        }
        tableau[i][j] = key;

        return;
    }

    // find the max among the tableau[i][j], tableau[i-1][j], tableau[i][j-1].
    // if tableau[i][j] is not the max, swap it with the maximum and recursive
    int max_position_x = i, max_position_y = j;
    if (tableau[max_position_x][max_position_y] < tableau[i - 1][j]) {
        max_position_x = i - 1; max_position_y = j;
    }
    if (tableau[max_position_x][max_position_y] < tableau[i][j - 1]) {
        max_position_x = i; max_position_y = j - 1;
    }

    // it means the young tableau is ordered
    if (max_position_x == i && max_position_y == j) {
        return;
    }

    swap(&tableau[i][j], &tableau[max_position_x][max_position_y]);
    PercolateUp(tableau, max_position_x, max_position_y);
}

分析此算法在最差情况下的时间复杂度：

定义 \(T(p)\) 为任一 \(M \times N\) Young tableau上的时间复杂度，其中 \(p = m + n\)

\[\begin{equation} T(p) = \left\{ \begin{array}{ll} \Theta(1) & p = 0 \\ T(p-1) + \Theta(1) & p \ge 1 \end{array} \right. \end{equation} \\ \Rightarrow T(p) = \Theta(p) = \Theta(m + n)\]

下滤

与上滤基本相同,注意边界条件的改变即可

void PercolateDown(ElementType tableau[][N], int i, int j) {
    // at the bottom border
    if (i == M - 1) {
        ElementType key = tableau[i][j];
        for (; j < N - 1 && tableau[i][j + 1] < key; j++) {
            tableau[i][j] = tableau[i][j + 1];
        }
        tableau[i][j] = key;

        return;
    }

    // at the right border
    if (j == N - 1) {
        ElementType key = tableau[i][j];
        for (; i < M - 1 && tableau[i + 1][j] < key; i++) {
            tableau[i][j] = tableau[i + 1][j];
        }
        tableau[i][j] = key;

        return;
    }


    // find the min among the tableau[i][j], tableau[i+1][j], tableau[i][j+1].
    // if tableau[i][j] is not the min, swap it with the minimum and recursive
    int min_position_x = i, min_position_y = j;
    if (tableau[i + 1][j] < tableau[min_position_x][min_position_y]) {
        min_position_x = i + 1, min_position_y = j;
    }
    if (tableau[i][j + 1] < tableau[min_position_x][min_position_y]) {
        min_position_x = i, min_position_y = j + 1;
    }

    if (min_position_x == i && min_position_y == j) {
        return;
    }

    swap(&tableau[i][j], &tableau[min_position_x][min_position_y]);
    PercolateDown(tableau, min_position_x, min_position_y);

}

此算法在最差情况下的时间复杂度： \(T(p) = \Theta(m + n)\)

插入

插入某元素可以很简单得由上滤得到，即将新插入的元素置于Young tableau的右下角，即设其为最大值，而后对其执行上滤操作。即可插入该值。

注意，根据Young tableau的性质，若右下角元素不为”空穴”，则表明整个表满了。不可继续执行Insert操作。

void Insert(ElementType tableau[][N], ElementType ele){
    if (tableau[M - 1][N - 1] != INF) {
        printf("the young tableau is full!");
        return;
    }

    tableau[M-1][N-1] = ele;
    PercolateUp(tableau, M - 1, N - 1);
}

此算法在最差情况下的时间复杂度： \(T(p) = \Theta(m + n)\)

取最小值

根据Young tableau的性质，第 \((0, 0)\) 个元素即为最小值。取出该值后，应使其保持有序，采取与二叉堆类似的做法，将其赋值为 \(\infty\) ，即设为空穴。而后将此元素下滤，即可保证Young tableau的有序性

ElementType ExtractMin(ElementType tableau[][N]) {
    ElementType min = tableau[0][0];

    tableau[0][0] = INF;
    PercolateDown(tableau, 0, 0);

    return min;
}

此算法在最差情况下的时间复杂度： \(T(p) = \Theta(m + n)\)

排序

使用一个 \(n \times n\) 的Young tableau，即可完成对 \(n^{2}\) 个数进行排序。时间复杂度为 \(\Theta(n^{3})\)

首先，将含有 \(n^{2}\) 个数的数组转化为一个Young tableau。采取不断将数组中的元素插入进一个空Young tableau中的方法实现

void ConvertArrayToYoungTableau(ElementType tableau[][N], const ElementType array[], int length) {
    if (length > M * N) {
        printf("the array is too long!");
        return;
    }

    for (int i = 0; i < length; ++i) {
        Insert(tableau, array[i]);
    }
}

此算法在最差情况下的时间复杂度： \(T(p) = \Theta(n^{3})\)

注意，此时一次插入的时间复杂度为 \(\Theta(n)\) ,而数组长度为 \(n^{2}\)

将该排序好的Young tableau不断的取出最小值，最终即可得到一个排好序数组。

具体方法实现如下：

void Sort(ElementType array[], int length) {
    ElementType tableau[M][N];
    InitTableau(tableau);

    ConvertArrayToYoungTableau(tableau, array, length);

    // it means the tableau is empty
    if (tableau[0][0] == INF) {
        return;
    }

    for (int i = 0; i < length; ++i) {
        array[i] = ExtractMin(tableau);
    }
}

此算法在最差情况下的时间复杂度： \(T(p) = \Theta(n^{2}) + \Theta(n^{3}) + \Theta(n^{3}) = \Theta(n^{3})\)

查找

从Young tableau的右上角 \((0, n-1)\) 开始, 进行查找. 如果要查找的数字大于它, 则根据Young氏的性质, 该数字大于这一行的所有数. 反之,如果要查找的数小于它, 则说明该数字小于这一列的所有数. 因此, 每次能排除一行或者一列.

bool Find(ElementType tableau[][N], const ElementType target) {
    int i = 0, j = N - 1;
    while(i < M || j >= 0) {
        ElementType cur = tableau[i][j];
        if (target == cur) {
            return true;
        }else if (target < cur) {
            --j;
        }else {
            ++i;
        }
    }
    return false;
}

此算法在最差情况下的时间复杂度： \(T(p) = \Theta(m + n)\)

Reference