heapsort

#include <stdio.h>

#define NMAX 100000

int a[NMAX + 1];
int n;


void insert(int m) {
  int i, j, aux;

  i = m;
  j = i >> 1;
  while ((j > 0) && (a[j] > a[i])) {
    aux = a[j]; a[j] = a[i]; a[i] = aux;

    i = j;
    j = i >> 1;
  }
}

void push(int m) {
  int i, j, aux;

  i = 1;
  j = i << 1;
  while (j <= m) {
    if ((j < m) && (a[j] > a[j + 1])) {
      j++;
    }

    if (a[i] > a[j]) {
      aux = a[i]; a[i] = a[j]; a[j] = aux;

      i = j;
      j = i << 1;
    } else {
        j = m + 1;
    }
  }
}


int main() {
  FILE *fin, *fout;
  int n, i, aux;

  fin = fopen("heapsort.in", "r");
  fout = fopen("heapsort.out", "w");

  fscanf(fin, "%d", &n);
  for (i = 1; i <= n; i++) {
    fscanf(fin, "%d", &a[i]);
  }

  for (i = 2; i <= n; i++) {
    insert(i);
  }

  for (i = n; i > 1; i--) {
    aux = a[1]; a[1] = a[i]; a[i] = aux;

    push(i - 1);
  }

  for (i = 1; i <= n; i++) {
    fprintf(fout, "%d ", a[i]);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}