#include <stddef.h>
#include <inttypes.h>

void downHeap(int64_t *, size_t, size_t);
void heapSort(int64_t *, size_t);

void downHeap(int64_t *a, size_t k, size_t n)
{
	size_t i;
	int64_t tmp = a[k];

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

void heapSort(int64_t *a, size_t n)
{
	size_t i = --n / 2;

	do
		downHeap(a, i, n);
	while (--i);
	do {
		int64_t tmp;
		downHeap(a, 0, n);
		tmp = a[n];
		a[n] = a[0];
		a[0] = tmp;
	} while (--n);
}