6-3 Young tableaus¶
An $m \times n$ Young tableau is an $m \times n$ matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be $\infty$, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold $r \leq mn$ finite numbers.
a. Draw a $4\times 4$ Young tableau containing the elements $\lbrace 9, 16, 3, 2, 4, 8, 5, 14, 12 \rbrace$.
b. Argue that an $m\times n$ Young tableau $Y$ is empty if $Y [1,1] = \infty$. Argue that $Y$ is full (contains $mn$ elements) if $Y[m,n] < \infty$.
c. Give an algorithm to implement EXTRACT-MIN on a nonempty $m \times n$ Young tableau that runs in $O(m+n)$ times. Your algorithm should use a recursive subroutine that solves an $m\times n$ problem by recursively solving either an $(m-1)\times n$ or an $m \times (n-1)$ subproblem. (Hint: Think about MAX-HEAPIFY.) Explain why your implementation of EXTRACT-MIN runs in $O(m+n)$ time.
d. Show how to insert a new element into a nonfull $m\times n$ Young tableau in $O(m+n)$ time.
e. Using no other sorting method as a subroutine, show how to use an $n\times n$ Young tableau to sort $n^2$ numbers in $O(n^3)$ time.
f. Give an $O(m+n)$-time algorithm to determine whether a given number is stored in a given $m\times n$ Young tableau.
a¶
$$ \begin{matrix} 2 & 3 & 4 & 5\cr 8 & 9 & 12 & 14\cr 16 & \infty & \infty & \infty\cr \infty & \infty& \infty & \infty\cr \end{matrix} $$
b¶
For $1\leq i \leq m$ and $1 \leq j \leq n$
$$ \begin{aligned} Y[i,j] & \geq Y[1,j]\cr & \geq Y[1,1]\cr Y[i,j] & \leq Y[m,j]\cr & \leq Y[m,n]\cr \end{aligned} $$
If $Y [1,1] = \infty$, then $Y[i,j] \geq Y[1,1] = \infty$, which implies $Y$ is empty.
$Y [m,n] < \infty \implies Y[i,j] \leq Y [m,n] < \infty$, which implies $Y$ is full.
c¶
YOUNG-TABLEAUS-EXTRACT-MIN(Y,m,n)
min = Y[1,1]
Y[1,1] = Y[m,n]
Y[m,n] = ∞
YOUNG-TABLEAUSIFY(Y,1,1)
return min
YOUNG-TABLEAUSIFY(Y,i,j)
if i < 1 or i > m or j < 1 or j > n
error "out of bounds"
index type {x,y}
min = {i , j}
if i < m and Y[i+1,j] < Y[min.x, min.y]
min = {i+1 , j}
if j < n and Y[i,j+1] < Y[min.x, min.y]
min = {i , j+1}
if min != {i , j}
exchange A[i,j] with A[min.x, min.y]
YOUNG-TABLEAUSIFY(Y,min.x,min.y)
$T(m+n) = T (m+n-1) + O(1) \implies T(m+n) = O(m+n)$
d¶
YOUNG-TABLEAUS-INSERT(Y,x,m,n)
if Y[m,n] = ∞
error "overflow"
YOUNG-TABLEAUS-DECREASE-KEY(Y,x,m,n)//O(m+n)
YOUNG-TABLEAUS-DECREASE-KEY(Y,x,i,j)
if i < 1 or i > m or j < 1 or j > n
error "out of bounds"
if Y[i,j] < x
error "invalid value"
index type {x,y}
max = {i , j}
if i > 1 and Y[i-1,j] > Y[max.x, max.y]
max = {i-1 , j}
if j > 1 and Y[i,j-1] > Y[max.x, max.y]
max = {i , j-1}
while max != {i , j}//O(i+j)
exchange A[i,j] with A[max.x, max.y]
i = max.x
j = max.y
if i > 1 and Y[i-1,j] > Y[max.x, max.y]
max = {i-1 , j}
if j > 1 and Y[i,j-1] > Y[max.x, max.y]
max = {i , j-1}
e¶
YOUNG-TABLEAUX-SORT(A,n)
creat an empty n*n size YOUNG-TABLEAUX Y
for i = 1 to n*n//O(n^3)
YOUNG-TABLEAUS-INSERT(Y,A[i],n,n)//O(n)
for i = 1 to n*n//O(n^3)
A[i] = YOUNG-TABLEAUS-EXTRACT-MIN(Y,n,n)//O(n)