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

template<typename T>
void heapsort (T a[], int n) {
  // build heap
  for (int i=n/2-1; i>=0; --i)
    down (a, n, i);

  for (int i=n-1; i>0; --i) {
    T t=a[i]; a[i]=a[0]; a[0]=t; // swap
    down (a, i-1, 0);
  }
}

template<typename T>
void down (T a[], int n, int i) {
  T t = a[i];
  while (i < n/2) {
    int j = 2*i+1;
    if (j+1<n && a[j] < a[j+1]) ++j;
    if (t>=a[j]) break;
    a[i]=a[j]; i=j;
  }
  a[i]=t;
}

// test
int main() {
  int A[100];
  for (int i=0; i<100; i++) A[i] = rand()%100;

  heapsort<int> (A, 100);  // sort numbers

  // output
  for (int i=0; i<100; i++) printf ("%i ", A[i]);
  printf ("\n");

  return 0;
}