a）不唯一2    3    4    58    9    12    14    16    c）提取Y[1][1]，并用ox7FFFFFFF填充。然后向右下调整YOUNG-EXTRACR-MIN(Y)1    if  Y[1][1] == 0X7FFFFFFF2        then error "heap underflow"3    min <- Y[1][1]4    A[1][1] <- 0X7FFFFFFF5    MAX-HEAPIFY(Y, 1, 1)6    return min//递归MIN-YOUNGIFY(Y, i, j) 1    min <- Y[i][j] 2    mini <- i 3    minj <- j 4    if i < m and Y[i+1][j] < min 5        mini <- i+1 6        minj <- j 7        min <- Y[i+1][j] 8    if j < n and Y[i+1][j+1] < min 9        mini <- i10        minj <- j+111        min <- Y[i][j+1]12    if i != mini or j != minj13        exchange Y[i][j] <-> Y[mini][minj]14        MIN-YOUNGIFY(Y, mini, minj)d）//若表未满，插入到右下角，然后向左上调整MIN-YOUNG-INSERT(Y, key) 1    if Y[m][n] < 0x7fffffff 2        then error "young overflow" 3    Y[m][n] <- key 4    flag <-  true 5    i <- m 6    j <- n 7    max <- key 8    maxi <- i 9    maxj <- j10    while true11        if i > 1 and max < Y[i-1][j]12            maxi <- i - 113            maxj <- j14            max <- Y[i-1][j]15        if j > 1 and max < Y[i][j-1]16            maxi <- i17            maxj <- j-118            max <- Y[i][j-1]19        if max == Y[i][j]20            break21        exchange Y[maxi][maxj] <-> Y[i][j]22        i <- maxi23        j <- maxj24        max <- Y[i][j]e）排序过程为：取下矩阵Y[1][1]元素，O(1)将Y[1][1]置为0x7FFFFFFF，O(1)调整矩阵，O(n)对n^2个结点各执行一次，因此时间为O(n^3)f）从左下角开找，若比它小，则向上，则比它大，则向右找FIND-YOUNG-KEY(Y, key) 1    i <- m 2   j <- 0 3   while i >= 1 and j <= n 4       if Y[i][j] = key 5       then return true 6       else if Y[i][j] < key 7       then j++ 8       else if Y[i][j] > key 9       then i--10   return false

//头文件#include <iostream>#include <stdio.h>using namespace std;//宏定义#define N 100class Young{    public:    //成员变量    int Y[N+1][N+1];    int m, n;    //构造与析构    Young(){}    Young(int a, int b);    //Heap(int size):length(size),heap_size(size){}    ~Young(){}    //功能函数    void Min_Youngify(int i, int j);    void Build_Min_Young();    void YoungSort();    bool Find_Young_key(int key);    //优先队列函数    void Young_Decrease_Key(int i, int j, int key);    void Min_Young_Insert(int key);    int Young_Minimum();    int Young_Extract_Min();    void Young_Delete(int i, int j);    //辅助函数    void Print();};Young::Young(int a, int b):m(a),n(b){    int i, j;    for(i = 1; i <= m; i++)    {        for(j = 1; j <= n; j++)            Y[i][j] = 0x7fffffff;    }}void Young::Build_Min_Young(){    int i, j, s;    for(s = m + n; s >= 2; s--)    {        for(i = 1; i <= m; i++)        {            j = s - i;            if(j > n)continue;            if(j < 1)break;            Min_Youngify(i, j);        }    }}int Young::Young_Extract_Min(){    int Min = Y[1][1];    Y[1][1] = 0x7fffffff;    Min_Youngify(1, 1);    return Min;}void Young::Min_Youngify(int i, int j){    int Min = Y[i][j], mini = i, minj = j;    if(i+1 < m && Y[i+1][j] < Min)    {        mini = i + 1;        minj = j;        Min = Y[i+1][j];    }    if(j+1 < n && Y[i][j+1] < Min)    {        mini = i;        minj = j + 1;        Min = Y[i][j+1];    }    if(i != mini || j != minj)    {        swap(Y[i][j], Y[mini][minj]);        Min_Youngify(mini, minj);    }}void Young::Min_Young_Insert(int key){    if(Y[m][n] < 0x7fffffff)    {        cout<<"error:young overflow"<<endl;        return ;    }    Y[m][n] = key;    int i = m, j = n, Max = key, maxi = i, maxj = j;    while(true)    {        if(i > 1 && Max < Y[i-1][j])        {            maxi = i - 1;            maxj = j;            Max = Y[i-1][j];        }        if(j > 1 && Max < Y[i][j-1])        {            maxi = i;            maxj = j - 1;            Max = Y[i][j-1];        }        if(Max == Y[i][j])            break;        swap(Y[maxi][maxj], Y[i][j]);        i = maxi;        j = maxj;        Max = Y[i][j];    }}bool Young::Find_Young_key(int key){    int i = m, j = 0;    while(i >= 1 && j <= n)    {        if(Y[i][j] == key)            return true;        else if(Y[i][j] < key)            j++;        else if(Y[i][j] > key)            i--;    }    return false;}void Young::Print(){    int i, j;    for(i = 1; i <= m; i++)    {        for(j = 1; j <= n; j++)            cout<<Y[i][j]<<‘ ‘;        cout<<endl;    }}void Young::Young_Delete(int i, int j){    Y[i][j] = 0x7fffffff;    Min_Youngify(i, j);}void Young::Young_Decrease_Key(int i, int j, int key){    if(key > Y[i][j])    {        cout<<"error:new key is larger than current key"<<endl;        return ;    }    Y[i][j] = key;    int Max = key, maxi, maxj;    while(true)    {        if(i > 1 && Max < Y[i-1][j])        {            maxi = i - 1;            maxj = j;            Max = Y[i-1][j];        }        if(j > 1 && Max < Y[i][j-1])        {            maxi = i;            maxj = j - 1;            Max = Y[i][j-1];        }        if(Max == key)            break;        swap(Y[maxi][maxj], Y[i][j]);        i = maxi;        j = maxj;    }}int Young::Young_Minimum(){    return Y[1][1];}void Young::YoungSort(){    while(Y[1][1] != 0x7fffffff)    {        cout<<Young_Extract_Min()<<‘ ‘;    }    cout<<endl;}

#include <iostream>#include "Young.h"using namespace std;int main(){    int m, n, x;    char c;    cin>>m>>n;    //输入随机测试数据    Young *Y = new Young(m, n);    int i, j;    for(i = 1; i <= m; i++)    {        for(j = 1; j <= n; j++)            Y->Y[i][j] = rand() % 100;    }    Y->Print();    //建堆    Y->Build_Min_Young();    Y->Print();    //测试成员函数    while(cin>>c)    {        switch(c)        {        case ‘E‘:            cout<<Y->Young_Extract_Min()<<endl;            break;        case ‘P‘:            Y->Print();            break;        case ‘I‘:            x = rand() % 100;            cout<<x<<endl;            Y->Min_Young_Insert(x);            break;        case ‘F‘:            cin>>x;            cout<<Y->Find_Young_key(x)<<endl;            break;        }    }    return 0;}

#include <vector>using namespace std;#define SIZE_OF_YOUNG 100#define INIT_DATA 0x7fffffffenum errorType{    SUCCESS = 0,    SIZE_OVERFLOW,    OUT_OF_SIZE,    PARAM_ERROR,};struct structCoordinate{    int h_index;    int w_index;    structCoordinate(int h, int w):h_index(h),w_index(w){}};class Young{        int Y[SIZE_OF_YOUNG+1][SIZE_OF_YOUNG+1];    int height, width;    bool isInRange(structCoordinate position);    void build();    void YoungifyWithSon(structCoordinate position);    void YoungifyWithParent(structCoordinate position);    void setDataInPosition(structCoordinate position, int data);    int getDataFromPosition(structCoordinate position);    void swapDatainPosition(structCoordinate c1, structCoordinate c2);    void Print();public:    Young(int h = SIZE_OF_YOUNG, int w = SIZE_OF_YOUNG);    void fillData(int *data, int size);    int extractMin();    bool findKey(int key);    errorType insert(int key);    errorType decreaseKey(structCoordinate position, int key);    int getMinimum();    vector<int> sort();    errorType deleteData(structCoordinate position);};

#include "Young.h"#include <iostream>using namespace std;enum directionType{    EAST = 0,    SOUTH,    WEST,    NORTH};structCoordinate directionStep[4] = {structCoordinate(0, 1),                                    structCoordinate(1, 0),                                    structCoordinate(0, -1),                                    structCoordinate(-1, 0)};structCoordinate getNeibourCoordinate(directionType direction, structCoordinate currentPosition){    currentPosition.h_index += directionStep[direction].h_index;    currentPosition.w_index += directionStep[direction].w_index;    return currentPosition;}Young::Young(int h, int w):height(h),width(w){    if(height < 1 || height > SIZE_OF_YOUNG)        height = SIZE_OF_YOUNG;    if(width < 1 || width > SIZE_OF_YOUNG)        width = SIZE_OF_YOUNG;    for(int i = 1; i <= height; i++)        for(int j = 1; j <= width; j++)            Y[i][j] = INIT_DATA;}void Young::fillData(int *data, int size){    int i, j, cnt = 0;    for(i = 1; i <= height; i++)    {        if(cnt >= size)            break;        for(j = 1; j <= width; j++)        {            if(cnt >= size)                break;            Y[i][j] = data[cnt];            cnt++;        }    }    build();}int Young::extractMin(){    structCoordinate minDataPosition(1, 1);    int minData =http://www.mamicode.com/ getDataFromPosition(minDataPosition);    setDataInPosition(minDataPosition, INIT_DATA);    YoungifyWithSon(minDataPosition);    return minData;}bool Young::findKey(int key){    structCoordinate currentPosition(height, 1);    while(isInRange(currentPosition) == true)    {        if(getDataFromPosition(currentPosition) == key)            return true;        else if(getDataFromPosition(currentPosition) < key)            currentPosition = getNeibourCoordinate(EAST, currentPosition);        else if(getDataFromPosition(currentPosition) > key)            currentPosition = getNeibourCoordinate(NORTH, currentPosition);    }    return false;}errorType Young::insert(int key){    structCoordinate currentPosition(height, width);    if(getDataFromPosition(currentPosition) < INIT_DATA)        return SIZE_OVERFLOW;    setDataInPosition(currentPosition, key);    YoungifyWithParent(currentPosition);    return SUCCESS;}errorType Young::decreaseKey(structCoordinate position, int key){    if(false == isInRange(position))        return OUT_OF_SIZE;    if(getDataFromPosition(position) < key)        return PARAM_ERROR;    setDataInPosition(position, key);    YoungifyWithParent(position);    return SUCCESS;}int Young::getMinimum(){    return Y[1][1];}vector<int> Young::sort(){    vector<int> ret;    while(getMinimum() != INIT_DATA)    {        ret.push_back(extractMin());    }    return ret;}errorType Young::deleteData(structCoordinate position){    if(false == isInRange(position))        return OUT_OF_SIZE;    if(getDataFromPosition(position) == INIT_DATA)        return PARAM_ERROR;    setDataInPosition(position, INIT_DATA);    YoungifyWithSon(position);}bool Young::isInRange(structCoordinate position){    if(position.h_index < 1 || position.w_index < 1)        return false;    if(position.h_index > height || position.w_index > width)        return false;    return true;}void Young::build(){    int h, w, step;    int maxHeight = height, minHeight = 1;    int maxWidth = width, minWidth = 1;    int maxStep = maxHeight + maxWidth;    int minStep = minHeight + minWidth;    for(step = maxStep; step >= minStep; step--)    {        for(h = minHeight; h <= maxHeight; h++)        {            w = step - h;            if(w > maxWidth)continue;            if(w < minWidth)break;            YoungifyWithSon(structCoordinate(h, w));        }    }}void Young::YoungifyWithSon(structCoordinate position){    int Min = getDataFromPosition(position);    int i = position.h_index, j = position.w_index;    structCoordinate minDataPosition = position;    structCoordinate southNeibour = getNeibourCoordinate(SOUTH, position);    if(isInRange(southNeibour) &&        getDataFromPosition(southNeibour) < getDataFromPosition(minDataPosition))    {        minDataPosition = southNeibour;    }    structCoordinate eastNeibour = getNeibourCoordinate(EAST, position);    if(isInRange(eastNeibour) &&        getDataFromPosition(eastNeibour) < getDataFromPosition(minDataPosition))    {        minDataPosition = eastNeibour;    }    if(getDataFromPosition(position) != getDataFromPosition(minDataPosition))    {        swapDatainPosition(position, minDataPosition);        YoungifyWithSon(minDataPosition);    }}void Young::YoungifyWithParent(structCoordinate position){    structCoordinate maxDataPosition = position;    while(true)    {        structCoordinate northNeibour = getNeibourCoordinate(NORTH, position);        if(isInRange(northNeibour) &&             getDataFromPosition(maxDataPosition) < getDataFromPosition(northNeibour))        {            maxDataPosition = northNeibour;        }        structCoordinate westNeibour = getNeibourCoordinate(WEST, position);        if(isInRange(westNeibour) &&             getDataFromPosition(maxDataPosition) < getDataFromPosition(westNeibour))        {            maxDataPosition = westNeibour;        }        if(getDataFromPosition(maxDataPosition) == getDataFromPosition(position))            break;        swapDatainPosition(maxDataPosition, position);        position = maxDataPosition;    }}void Young::setDataInPosition(structCoordinate position, int data){    Y[position.h_index][position.w_index] = data;}int Young::getDataFromPosition(structCoordinate position){    return Y[position.h_index][position.w_index];}void Young::swapDatainPosition(structCoordinate c1, structCoordinate c2){    int data1 = getDataFromPosition(c1);    int data2 = getDataFromPosition(c2);    setDataInPosition(c1, data2);    setDataInPosition(c2, data1);}void Young::Print(){    for(int i = 1; i <= height; i++)    {        for(int j = 1; j <= width; j++)            cout<<Y[i][j]<<‘ ‘;        cout<<endl;    }}