typedef struct {
    KeyType key;
    InfoType otherInfo;
} RedType;

typedef struct {
    RedType r[MAX_SIZE + 1];
    int length;
} SqList;
void select_sort(SqList &L) {
    for (int i = 1; i < L.length; i++) {
        int min = i;
        for (int j = i + 1; j <= L.length; j++) {
            if (L.r[j].key < L.r[min].key) {
                min = j;
            }
        }
        if (min != i) {
            std::swap(L.r[i], L.r[min]);
        }
    }
}

KeyType getWinner(KeyType *tree, int length, int i, int j) {
    int iIndex = (i >= (length)) ? i : tree[i];
    int jIndex = (j >= (length)) ? j : tree[j];
    if (tree[iIndex] <= tree[jIndex]) return iIndex;
    return jIndex;
}

void creat_tree(SqList L, KeyType *tree, int length) {
    for (int i = 0; i <= length; i++) {
        tree[i + length] = L.r[i+1].key;
    }
    for (int i = length * 2-1; i > 1; i -= 2) {
        int p = i / 2;
        int j = i - 1;
        int w = getWinner(tree, length, i, j);
        tree[p] = w;
    }
}

void tree_select_sort(SqList &L) {
    KeyType tree[L.length * 2 ]={0};
    creat_tree(L, tree, L.length);
    for (int i = 1; i <= L.length; ++i) {
        int champion = tree[tree[1]];
        tree[tree[1]] = INT_MAX;
        L.r[i].key = champion;
        if (i == L.length) break;
        int champion_i = tree[1];
        while (champion_i > 1) {
            int k = champion_i / 2;
            int j = 0;
            if (champion_i % 2 == 0 && champion_i < 2 * L.length) {
                j = champion_i + 1;
            } else j = champion_i - 1;
            tree[k] = getWinner(tree, L.length, champion_i, j);
            champion_i = k;
        }
    }
}