#include <stdio.h>
#include <stdlib.h>
#define FILENAME "test.txt"
#define N 1024
void readfile(int *n, int (**a)[]) {
  static char buff[N];
  FILE *fp;
  if ((fp = fopen(FILENAME, "r")) != 0) {
    fgets(buff, N, fp);
    if (sscanf(buff, "%d", n) == 1) {
      int i;
      if ((*a = malloc(sizeof(int) * (*n))) == 0) { /* abnormal */
        *a = 0;
        return;
      }
      for (i = 0; i < *n; i++) {
        fgets(buff, N, fp);        
        if (sscanf(buff, "%d", &(**a)[i]) != 1) { /* abnormal */
          *n = i;
          return;
        }
      }
      fprintf(stderr, "done reading.\n");
    }
    fclose(fp);
  }
}

void vomit(int p, int level, int n, int (*a)[]) {
  int i;
  if (p < n) {
    vomit(2 * p + 1, level + 2, n, a);
    for (i = 0; i < level; i++)
      printf("  ");
    printf("%d\n", (*a)[p]);
    vomit(2 * p + 2, level + 2, n, a);
  }
#if 0
  int i;
  printf("> ");
  for (i = 0; i < n; i++)
    printf("%d ", (*a)[i]);
  putchar('\n');
#endif
}

void swap(int *a, int *b) {
  int t;
  printf("%d<->%d\n", *a, *b);
  t = *a;
  *a = *b;
  *b = t;
}

int compare(int a, int b) {
  return a < b;
}

void task_heap(int *n, int (**a)[]) {
  int idx, m, p, i;

  vomit(0, 0, *n, *a);
  printf("---------------------------------\n");

  /* initial */
  if (*n >= 2 && compare((**a)[1], (**a)[0])) {
    swap(&(**a)[0], &(**a)[1]); printf("*1\n");
  }
  if (*n >= 3 && compare((**a)[2], (**a)[0])) {
    swap(&(**a)[0], &(**a)[2]); printf("*2\n");
  }
  /* forward step */
  if (*n >= 4) {
    for (idx = 3; idx < *n; idx++) {
      for (m = idx; m > 0;  m = p) {
        p = (m - 1) / 2;
        if (compare((**a)[m], (**a)[p])) {
          swap(&(**a)[m], &(**a)[p]);
          vomit(0, 0, *n, *a);
          printf("---------------------------------\n");
        }
      }
    }
  } /* if (*n >= 4) { */
  /* backward */
  for (idx = *n - 1; idx > 0; --idx) {
    printf("drawing top\n");
    swap(&(**a)[0], &(**a)[idx]);
    vomit(0, 0, idx, *a);                      
    printf("---------------------\n");
    for (p = 0; 2 * p + 1 < idx; /* nothing */) {
      if (2 * p + 2 < idx) {
        if (compare((**a)[2 * p + 1], (**a)[2 * p + 2])) {
        label:
          if (compare((**a)[2 * p + 1], (**a)[p])) {
            swap(&(**a)[p], &(**a)[2 * p + 1]);
            p = 2 * p + 1;
          } else
            break;
        } else {
          if (compare((**a)[2 * p + 2], (**a)[p])) {
            swap(&(**a)[p], &(**a)[2 * p + 2]);
            p = 2 * p + 2;
          } else
            break;
        }
        vomit(0, 0, idx, *a);                      
        printf("---------------------\n");
        continue;
      } else {
        goto label;
      }
    }
  }
  for (i = 0; i < *n; i++)
    printf("%d, ", (**a)[i]);
  putchar('\n');
}

int main() {
  int n, (*a)[];
  a = 0;
  readfile(&n, &a);
  if (a != 0) {
    task_heap(&n, &a);
    free(*a);
  }
  return 0;
}
/* end */