#include <stdio.h>
#define SIZE 256

typedef struct int_heap 
{
    int data[SIZE+1];
    int count;
} HEAP;


/* これを完成させよ */
void append(HEAP *p, int x)
{
    (p->count)++;
}


/* こちらは既に完成している */
int get_min(HEAP *p)
{
    int min, idx, tmp, parent, child, left, right;

    /* まず，ヒープの根の値を最小値として抽出 */
    min = p->data[1];

    /* 次に，ヒープの末尾のデータをいったん根へ移動させ，個数は -1 する */
    p->data[1] = p->data[p->count];
    (p->count)--;

    /* 親子関係（親の方が子より小さい）に矛盾がなくなるまで交換を繰り返す */
    parent = 1;
    while (1)
    {
        left = parent*2;
        right = left+1;

        /* 子がいない場合，そこで終了 */
        if ( left > p->count )
        {
            break;
        }

        /* 左の子と右の子で小さい方を child とする */
        child = left;
        if ( right <= p->count && p->data[right] < p->data[left] )
        {
            child = right;
        }

        /* 上で求めた child を親と比較し，交換が起きればそれを再び親として次の繰り返しへ */
        if ( p->data[child] < p->data[parent] )
        {
            tmp = p->data[child];
            p->data[child] = p->data[parent];
            p->data[parent] = tmp;
            parent = child;
        }
        else /* 上で交換が起こらなければそれで終了 */
        {
            break;
        }
    }

    return min;    
}

int main(void)
{
    int x;
    HEAP heap;

    heap.count = 0;

    printf("いくつか整数を入力してください（-1 で終了）:\n");
    while(1)
    {
        scanf("%d", &x);
        if ( x == -1 )
        {
            break;
        }
        append(&heap, x);
    }

    printf("ヒープソートの結果：\n");
    while(heap.count > 0)
    {
        printf("%d ", get_min(&heap));
    }
    printf("\n");

    return 0;
}