Fabrice E Iyolo

Turn coke into code


Young tableaus, one of the famous applications of the heap properties

A young tableau is a matrix (m x n) where the young tableau property (rows and columns of the matrix are sorted) is maintained. In order to maintain the Young tableau property we can consider any Young tableau as a modified heap, in which each element has two parent nodes (left and top), and two children nodes (right and down), so each element is then bigger or equals its parents nodes values and less or equals its children nodes values.


Minimum element of the young tableau ?

It obvious from the heap property of the Young Tableau that the element that is leftmost and topmost element is the minimum value in the tableau. That is, any element to the right of this element, or below it, is by definition greater than it. So, if Y [1, 1] = ∞, it means no Y [i, j] exist to the right or below it, thus the tableau is empty because the above property is true for any i and j.

Extract the minimum value of the young tableau

EXTRACT-MIN in a tableau is similar to the operation in a standard heap. The minimum value is retrieved from the cell Y[1,1], which is then set to ∞ . The value of ∞ is then percolated down the tableau by the youngify function, so that at each step the lesser of the children replaces the value. This is repeated until no elements that are less than ∞ are to the right or below it.

My java code for extract_min

    public static int extract_min(int [][]youngT){
        int x = youngT[0][0];
        youngT[0][0] = Integer.MAX_VALUE;
        youngify(youngT, 0, 0);
        return x;
    }

I think you've notice that the extract_min method called the youngify method which make sure that after extracting the mininum value, it replaces this values by the infinity and restart the process of building the young tableau again.

Here is the youngify function, java toujours

public static void youngify(int [][] young_t, int i, int j){
        int x, y;
        x = i;
        y = j;
        int temp;
        if (i + 1 < m){
            if (young_t[i][j] > young_t[i+1][j]){
                x = i + 1;
                y = j;
            }
        }
        
        if (j+1 < n){
            if (young_t[x][y] > young_t[i][j+1]){
                x = i;
                y = j+1;
            }
        }
        
        if(x != i || y != j){
            temp = young_t[x][y];
            young_t[x][y] = young_t[i][j];
            young_t[i][j] = temp;
            youngify(young_t, x, y);
        }
    }


Insertion

Insertion is done in a similar way than the standard heap. We first check if the Table is not full, then we insert this new value in the last cell Y [m, n], and percolating it up by the inverse of the youngify function until it is greater in value than both its parents. The inverse of the youngify function up will recursively exchange it with the greater of its two parents.

Here is my java code to insert in a young tableau

 public static void insert_key(int [][]young_t, int i, int j, int key){
        int x, y, max, temp;
        
        if (young_t[i][j] < key){
            System.out.println("No more insertions possible, The tableau is full");
            return;
        }
        young_t[i][j] = key;
        x = i;
        y = j;
        max = Integer.MAX_VALUE;
        
        while( (i > 0 || j > 0) && (max > young_t[i][j]) ){
            temp = young_t[x][y];
            young_t[x][y] = young_t[i][j];
            young_t[i][j] = temp;
            i = x;
            j = y;
                
            if (i - 1 >= 0 && young_t[i][j] < young_t[i-1][j]){
                x = i -1;
                y = j;
            }
                
            if(j -1 >= 0 && young_t[x][y] < young_t[i][j-1]){
                x = i;
                y = j - 1;
            }
            max = young_t[x][y];
        }
    }


Search a value

To search the tableau for a given value k, we can modify the Insert procedure given above slightly. The idea is to start off as if we are inserting k. While percolating it up, however, we check whether either of the parent cells is equal to k. If so, we have found the entry we were looking for. If not, we percolate up as before, and repeat. Note that we do not actually modify the tableau as we go along; the insertion and InverseYoungify are conceptual. If in this process we get to two parent cells which are both lesser in value than k, we conclude that k does not exist in the tableau. It is easily seen that this algorithm runs in the same time-bound as Insert.

Java code for search

    public static boolean search_key(int [][]young_t, int i, int j, int key){
        int start_x, start_y;
        
        start_x = i;
        start_y = j;
        
        if (i >=0 && j < n){
        
            if (young_t[i][j] == key){
                return true;
            }
            else if (young_t[i][j] < key) {
                return search_key(young_t, i, j+1, key);
            }
            else if (young_t[i][j] > key){
                return search_key(young_t, i - 1, j, key);
            }
            else return false;
        }
        else return false;
    }

All these operations are implemented in a Netbeans project, with GUI available here. Download and play with it.

 

 
A propos

Je suis techniquement fort, expérimenté, pratique et curieux. Je travaille depuis plus de 15 ans dans le domaine de technologies de l'information. Je suis passionné de technologie et de ses applications. J'ai des connaissances et des compétences étendues et approfondies dans les domaines de la cloud computing, des outils, de l'automatisation et de la business intelligence.

Contact