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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int KeyType;
typedef int InfoType;
typedef struct {
	KeyType key;
	InfoType otherinfo;
}RedType;
typedef struct {
	RedType r[MAXSIZE+1];
	int length;
}SqList;
typedef SqList HeapType;

Status LT(KeyType a, KeyType b)
{
	if(a<b)
		return TRUE;
	else
		return FALSE;
}

void ListInsert(SqList *L)
{
	int i, n;

	printf("Input number of key: ");
	scanf("%d", &n);
	if(n>MAXSIZE)
		exit(-1);
	L->r[0].key = 0;
	L->length = 0;
	for(i=1; i<=n; i++)
	{
		printf("Input key: ");
		scanf("%d", &L->r[i]);
		L->length++;
	}
}

void ListTraverse(SqList L)
{
	int i;
	for(i=1; i<=L.length; i++)
		printf("%d ", L.r[i].key);
	printf("\n");
}

void HeapAdjust(HeapType *H, int s, int m)
{
	int j;
	RedType rc;

	rc = H->r[s];
	for(j=2*s; j<=m; j*=2)
	{
		if(j<m && LT(H->r[j].key, H->r[j+1].key))
			j++;
		if(!LT(rc.key, H->r[j].key))
			break;
		H->r[s] = H->r[j];
		s = j;
	}
	H->r[s] = rc;
}

void HeapSort(HeapType *H)
{
	int i;
	RedType rc;

	for(i=H->length/2; i>0; i--)
		HeapAdjust(H, i, H->length);
	for(i=H->length; i>1; i--)
	{
		rc = H->r[1];
		H->r[1] = H->r[i];
		H->r[i] = rc;
		HeapAdjust(H, 1, i-1);
	}
}

void main()
{
	HeapType H;

	ListInsert(&H);
	HeapSort(&H);
	ListTraverse(H);
}