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

#define OK 1
#define OVERFLOW -2
#define ERROR -1

#define STACK_INIT_SIZE 4

#define K 5
#define MAXKEY INT_MAX
#define MINKEY INT_MIN

typedef int Status;
typedef struct{
	int* base;
	int* top;
	int stacksize;
}SqStack;

typedef int KeyType;
typedef int LoserTree[K];
typedef struct{
	KeyType key;
}ExNode, External[K+1];

Status InitStack(SqStack* S)
{
	S->base = (int*)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!S->base)
		exit(OVERFLOW);
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return OK;
}

Status Push(SqStack* S, int e)
{
	if(S->top-S->base >= S->stacksize)
		exit(OVERFLOW);
	*S->top++ = e;
	return OK;
}

Status Pop(SqStack* S, int* e)
{
	if(S->top == S->base)
		return ERROR;
	*e = *(--S->top);
	return OK;
}

void Adjust(LoserTree ls, External b, int s)
{
	int t;
	int tmp;

	t = (s+K)/2;
	while(t>0)
	{
		if(b[s].key > b[ls[t]].key)
		{
			tmp = s;
			s = ls[t];
			ls[t] = tmp;
		}
		t = t/2;
	}
	ls[0] = s;
}

void CreateLoserTree(LoserTree ls, External b)
{
	int i;

	b[K].key = MINKEY;
	for(i=0; i<K; i++)
		ls[i] = K;

	for(i=K-1; i>=0; i--)
		Adjust(ls, b, i);
}

void K_merge(LoserTree ls, External b, SqStack *S)
{
	int i, q;
	for(i=0; i<K; i++)
		Pop(&S[i], &b[i].key);

	CreateLoserTree(ls, b);
	while(b[ls[0]].key != MAXKEY)
	{
		q = ls[0];
		printf("%d ", b[q].key);

		Pop(&S[q], &b[q].key);
		Adjust(ls, b, q);
	}
	printf("\n");
}

void main()
{
	int i, j;
	int e;
	SqStack S[K];
	LoserTree ls;
	External b;

	for(i=0; i<K; i++)
	{
		j = 0;
		InitStack(&S[i]);
		Push(&S[i], MAXKEY);
		while(j++ < 3)
		{
			printf("S[%d] push: ", i);
			scanf("%d", &e);
			Push(&S[i], e);
		}
	}

	K_merge(ls, b, S);
}