/* ヒープ・ソート(改良選択法) */

#include  <stdio.h>

#define  N   5

int main(void)
{
        int  a[N + 1];
        int  n, i, s, p, m, tmp;

        printf("%d個の整数を入力して下さい。\n", N);
        for (n = 1; n <= N; n++){
                printf("No %d : ", n);
                scanf("%d", &a[n]);
                s = n;
                p = s / 2;
                while (s >= 2  &&  a[p] > a[s]){
                        tmp = a[p];
                        a[p] = a[s];
                        a[s] = tmp;
                        s = p;
                        p = s / 2;
                }
        }
        n--;
        m = n;
        while (n > 1){
                tmp = a[1];
                a[1] = a[n];
                a[n] = tmp;
                n--;

                p = 1;
                s = 2 * p;
                while (s <= n){
                        if (s < n  &&  a[s+1] < a[s])
                                s++;
                        if (a[p] <= a[s])
                                break;
                        tmp = a[p];
                        a[p] = a[s];
                        a[s] = tmp;
                        p = s;
                        s = 2 * p;
                }
        }

        puts("小さい順に並べ替えると");
        for (i = m; i >= 1; i--)
                printf("%5d", a[i]);
        printf("\n");

    return (0);
}