#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;
}