Յունգի աղյուսակ - Young tabelau

\(n\times m\) չափի \(A\) մատրիցը կոչվում է Յունգի աղյուսակ (Young tabelau), եթե նրա տարրերը տողերում կարգավորված են ձախից-աջ, իսկ սյուներում՝ վերևից-ներքև։ Եթե աղյուսակի մի որևէ վանդակ դատարկ է, ապա այն նշվում է \(\infty\) (անվերջություն) նշանով։ \(A\) Յունգի աղյուսակը համարվում է դատարկ, եթե \(A[0,0] = \infty\)։ Աղյուսակը համարվում է ամբողջովին լցված, եթե \(A[n-1,m-1] \ne \infty\)։ Աղյուսակի տարրերից կարգով ամենափոքրը միշտ գտնվում է \(A[0,0]\) բջջում։

Ահա Յունգի աղյուսակի մի նմուշ, որը պարունակում է \(0\), \(1\), \(2\), \(3\), \(5\), \(7\), \(9\) թվերը։

0	0	2	9
3	5	7	∞
∞	∞	∞	∞

Յունգի աղյուսակի հետ կատարվող տիպիկ գործողություններից կարելի է համարել նոր տարրի ավելացումը, մինիմալ տարրի հեռացումը, դատարկ կամ լցված լինելը ստուգելը։

Իրական թվերի համար նախատեսված Յունգի աղյուսակը կարելի է սահմանել C++ լեզվի հետևյալ դասով․

class Tabelau {
private:
    int rows;      // տողերի քանակը
    int columns;   // սյուների քանակը
    double** data; // տվյալների աղյուսակ

public:
    Tabelau( int, int );
    ~Tabelau();

    bool is_empty() const; // աղյուսակը դատարկ է
    bool is_full() const;  // աղյուսակը լցված է

    double minimum() const; // փոքրագույն տարրը
    void add( double );     // ավելացնել նոր տարր
    void remove();          // հեռացնել փոքրագույն տարրը

private:
    // աղյուսակի կարգավորում նոր տարրն ավելացնելուց հետո
    void add_aux( int, int );
    // աղյուսակի կարգավորում նոր տարրը հեռացնելուց հետո
    void remove_aux( int, int );
};

Դասի կոնստրուկտորի նպատակը նոր աղյուսակի ստեղծումն է, որի բոլոր բջիջները նախապես լրացված են \(\infty\) արժեքով։

Tabelau::Tabelau( int r, int c)
  : rows{r}, columns{c}
{
  data = new double*[rows];
  for( int i = 0; i < rows; ++i ) {
    data[i] = new double[columns];
    for( int j = 0; j < columns; ++j )
      data[i][j] = INFINITY;
  }
}

Դեստրուկտորը պարզապես ազատում է զբաղեցրած հիշողությունը։

Tabelau::~Tabelau()
{
    for( int i = 0; i < rows; ++i )
        delete[] data[i];
    delete[] data;
}

Աղյուսակի դատարկ լինելը ստուգվում է is_empty() մեթոդով, իսկ լցված լինելը՝ is_full() մեթոդով։

bool Tabelau::is_empty() const
{
  return data[0][0] == INFINITY;
}

bool Tabelau::is_full() const
{
  return data[rows-1][columns-1] != INFINITY;
}

Փոքրագույն տարրը վերադարձնում է minimum() մեթոդը․

double Tabelau::minimum() const
{
  return data[0][0];
}

\(A\) Յունգի աղյուսակում նոր տարրն ավելացվում է \(A[rows-1,columns-1]\) բջջում, այնուհետև այն փոխատեղվում է իրենից վերևում և ձախում գտնվող տարրերից մեծագույնի հետ։ Նույնը կրկնվում է այնքան անգամ, քանի դեռ դիտարկվող տարրից վերև կամ ձախ գոյություն ունի ավելի մեծ արժեքով տարր։

void Tabelau::add( double val )
{
  data[rows-1][columns-1] = val;
  add_aux( rows-1, columns-1 );
}

Նոր տարրը \(A[rows-1,columns-1]\) բջջում գրառելուց հետո աղյուսակի կարգավորումը կատարվում է add_aux() ռեկուրսիվ մեթոդով։

void Tabelau::add_aux( int r, int c )
{
  int k{r}, h{c};
  if( r > 0 && data[r][c] < data[r-1][c] )
    k = r - 1;
  if( c > 0 && data[k][h] < data[r][c-1] )
    k = r, h = c - 1;
  if( k != r || h != c ) {
    double temp{data[r][c]};
    data[r][c] = data[k][h];
    data[k][h] = temp;
    add_aux( k, h );
  }
}

Մինիմալ տարրը, որ միշտ գտնվում է \(A[0,0]\) բջջում, աղյուսակից հեռացնելու համար նրա տեղում գրվում է \(\infty\), և այդ պատճառով էլ խախտվում է Յունգի աղյուսակի հատկությունը։ Աղյուսակը նորից կարգավորելու համար պետք է \(\infty\) արժեքն այնքան ժամանակ տեղափոխել դեպի աջ կամ ներքև, քանի դեռ գոյություն ունի նրանից փոքր տարր։

void Tabelau::remove()
{
  data[0][0] = INFINITY;
  remove_aux( 0, 0 );
}

Տարրը հեռացնելուց հետո աղյուսակի կարգավորումը կատարվում է remove_aux() մեթոդով։

void Tabelau::remove_aux( int r, int c )
{
  int k{r}, h{c};
  if( r < rows - 1 && data[r][c] > data[r+1][c] )
    k = r + 1;
  if( c < columns - 1 && data[k][h] > data[r][c+1] )
    k = r, h = c + 1;
  if( k != r || h != c ) {
    double temp{data[r][c]};
    data[r][c] = data[k][h];
    data[k][h] = temp;
    remove_aux( k, h );
  }
}

Թերևս այսքանը Յունգի աղյուսակների մասին։ Նշեմ նաև, որ այն հաճախ օգտագործվում է նախապատվություններով հերթերի կազմակերպման և կարգավորման heap-sort ալգորիթմների իրականացման համար։