#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define N 26        /* ソートするものの個数 */
#define MAX 99      /* 数値データは 0 ... MAX */

#define swap(I,J) { int tmp = a[(I)]; a[(I)] = a[(J)]; a[(J)] = tmp; }

int myrand(int max);
void print(int j);
void heapsort(void);
void downheap(int i, int n);

int a[N];

main() {
    int i;

    srand((unsigned)time(NULL));        /* 現在時刻で乱数の種を初期化 */
    for (i=0; i<N; i++) {
        a[i] = myrand(MAX);
    }
    print(N);
    printf("これがソート前のデータです.\n");
    heapsort();
    print(N);
    printf("ソートは完了しました.\n");
    return;
}


/* 0 ... max の範囲の乱数を返す。max <= RAND_MAX でなければならない */
int myrand(int max) {
    int r;

    if (max == INT_MAX) {
        return rand();
    }

    while (1) {
        r = rand();
        if (RAND_MAX % (max+1) != max && r/(max+1) == RAND_MAX/(max+1)) {
            continue;
        } else {
            return r % (max+1);
        }
    }
}


/* 配列を印字。第 j 項以降は色がつく */
void print(int j) {
    int i;

    for (i=0; i<N; i++) {
        if (i == j) {
            printf("\033[93m");
        }
        printf(" %2d", a[i]);
    }
    printf("\033[m\n");
}


/* 配列 a[0] ... a[N-1] があったとする。任意の非負整数 i に対し a[i] の子は  */
/* a[2*i+1] および a[2*i+2] と定義する。a[j] の親は a[(j-1)/2] である。      */
/* a[k] から a[l] までがヒープであるとは、この範囲に含まれる任意の二元が親子 */
/* であるならば親が子以上であることをいう。                                  */

/* 配列のヒープソート */
void heapsort(void) {
    int i;

    for (i=N/2; i>=0; i--) {    /* ヒープの構成（＝全体を並べ替えてヒープに）*/
        downheap(i, N-1);
    }
    print(N);
    puts("ヒープが完成しました.");
    for (i=N-1; i>0; i--) {
        swap(0, i);
        print(i);
        printf("%d 項以降は決定しました.\n", i);
        downheap(0, i-1);       /* ヒープの再構成 */
        print(i);
        printf("第 0 項から第 %d 項までをヒープに再構成しました.\n", i-1);
    }
}


/* a[i] から a[n] までをヒープにする（←日本語が変かも）。a[i] の子から先の */
/* 世代はすでにヒープになっていると仮定する                                 */

void downheap(int i, int n) {
    print(n+1);
    if (2*i+1 > n) {    /* 子がないとき */
        return;
    }
    if (2*i+1 == n) {   /* 子が片方のみのとき */
        if (a[i] >= a[n]) { /* その子との間の大小関係 OK のとき*/
            return;
        } else {
            swap(i, n); return;
        }
    }

        /* ここにくるのは両方の子がいるとき */
    if (a[2*i+1] <= a[i]) {
        if (a[2*i+2] <= a[i]) {     /* a[i] が最大のとき */
            ;
        } else {        /* a[2*i+1] <= a[i] < a[2*i+2] のとき */
            swap(i, 2*i+2); downheap(2*i+2, n);
        }
    } else {            /* a[i] < a[2*i+1] のとき */
        if (a[2*i+2] <= a[i] || a[2*i+2] < a[2*i+1]) {
            swap(i, 2*i+1); downheap(2*i+1, n);
        } else {        /* a[i] < a[2*i+1] <= a[2*i+2] のとき */
            swap(i, 2*i+2); downheap(2*i+2, n);
        }
    }
}