#include <stdio.h>

void downheap(int a[], int n, int k)
{
	int j;

	while( k < n / 2 ) {
		j = 2 * k + 1;
		if( (j + 1) < n && a[j] < a[j + 1]) {
			j++;
		}
		if( a[k] >= a[j] ) {
			break;
		}
		a[k] ^= a[j] ^= a[k] ^= a[j];
	}
}

void heapsort(int a[], int n)
{
	int k;

	for(k = n / 2; k > 0; k--) {
		downheap(a, n, k);
	}

	for( ; n > 1; n--) {
		downheap(a, n, 0);
		a[0] ^= a[n - 1] ^= a[0] ^= a[n - 1];
	}

}

main()
{
	int a[] = { 9, 3, 7, 1, 8, 6, 2, 5, 4, 10 };
	int n = sizeof(a) / sizeof(int);

	heapsort(a, n);

	while(n--) {
		printf("%d ", a[n]);
	}
}