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

#define INFTY 1000000000

typedef struct _node {
   int key;
   struct _node *L, *R;
} tnode;

typedef tnode *bintree;

typedef struct {
   tnode *p;
   int l, r;
} qnode;

tnode *gennode ( int A[], int n )
{
   int i;
   tnode *p;

   p = (tnode *)malloc(sizeof(tnode));
   p -> L = p -> R = NULL;
   i = rand() % n;
   while (A[i] < 0) { ++i; if (i >= n) i -= n; }
   p -> key = A[i]; A[i] = -1;
   return p;
}

bintree buildtree ( int n )
{
   int *A, step, i, l, r;
   qnode *Q;
   int front, back;
   bintree T, p;

   A = malloc(n * sizeof(int));
   step = 900 / n;
   A[0] = 100 + rand() % step;
   for (i=1; i<n; ++i) A[i] = A[i-1] + 1 + (rand() % step);

   Q = (qnode *)malloc(n * sizeof(qnode));
   T = gennode(A,n);
   Q[0].p = T;
   Q[0].l = (n > 1) ? rand() % (n-1) : 0;
   Q[0].r = n - 1 - Q[0].l;
   front = back = 0;
   while (front <= back) {
      p = Q[front].p;
      l = Q[front].l;
      r = Q[front].r;
      printf("%3d %d %d\n", p -> key, (l == 0) ? 0 : 1, (r == 0) ? 0 : 1);
      ++front;
      if (l > 0) {
         ++back;
         Q[back].p = p -> L = gennode(A,n);
         Q[back].l = (l > 1) ? rand() % (l-1) : 0;
         Q[back].r = l - 1 - Q[back].l;
      }
      if (r > 0) {
         ++back;
         Q[back].p = p -> R = gennode(A,n);
         Q[back].l = (r > 1) ? rand() % (r-1) : 0;
         Q[back].r = r - 1 - Q[back].l;
      }
   }
   free(A); free(Q);
   return T;
}

void preorder ( bintree T )
{
   if (T == NULL) return;
   printf("%4d", T->key);
   preorder(T->L);
   preorder(T->R);
}

void inorder ( bintree T )
{
   if (T == NULL) return;
   inorder(T->L);
   printf("%4d", T->key);
   inorder(T->R);
}

void heapify ( bintree T, int limit )
{
   tnode *m, *p;
   int t;
   #ifdef __VERB
   int skipped = 0;
   #endif

   if ((T == NULL) || (T -> key >= limit)) return;
   m = T;
   p = T -> L; if ((p) && (p->key < limit) && (p->key > m->key)) m = p;
   p = T -> R;
   while (p) {
      if (p->key < limit) {
         if (p->key > m->key) m = p;
         break;
      } else {
         #ifdef __VERB
         printf("... skipped finished node\n");
         skipped = 1;
         #endif
         p = p->L;
      }
   }
   if (m == T) return;
   #ifdef __VERB
   if (skipped) printf("... Swapping %d with %d (non-child)\n", T->key, m->key);
   #endif
   t = T -> key; T -> key = m -> key; m -> key = t;
   heapify(m,limit);
}

void makeheap ( bintree T )
{
   if (T == NULL) return;
   makeheap(T->L);
   makeheap(T->R);
   heapify(T,INFTY);
}

int heapsort ( bintree T, tnode *p, int limit )
{
   if ((T == NULL) || (p == NULL) || (p -> key >= limit)) return limit;
   limit = heapsort(T,p->R,limit);
   #ifdef __VERB
   printf("\n... Old limit = %d\n", limit);
   #endif
   if (p == T) {
      #ifdef __VERB
      printf("... Changing root from %d to %d\n", T -> key, (T -> L) ? T -> L -> key : 0);
      #endif
      limit = T -> key; T = T -> L;
   } else {
      #ifdef __VERB
      printf("... Swapping %d with %d (root)\n", p -> key, T -> key);
      #endif
      limit = T -> key; T -> key = p -> key; p -> key = limit;
      heapify(T,limit);
      #ifdef __VERB
      printf("    Preorder :"); preorder(T); printf("\n");
      printf("    Inorder  :"); inorder(T); printf("\n");
      #endif
   }
   #ifdef __VERB
   printf("... New limit = %d\n", limit);
   #endif
   limit = heapsort(T,p->L,limit);
   return limit;
}

void heap2BST ( bintree T )
{
   heapsort(T,T,INFTY);
}

int isBST ( bintree T, int lb, int ub )
{
   if (T == NULL) return 1;
   if ((T -> key <= lb) || (T -> key >= ub)) return 0;
   return ((isBST(T->L,lb,T->key)) && (isBST(T->R,T->key,ub)));
}

int main ( int argc, char *argv[] )
{
   int n;
   bintree T;

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   if (n <= 0) n = 16;
   srand((unsigned int)time(NULL));

   T = buildtree(n);
   printf("\n+++ Initial binary tree\n");
   printf("    Preorder :"); preorder(T); printf("\n");
   printf("    Inorder  :"); inorder(T); printf("\n\n");

   makeheap(T);
   printf("\n+++ After conversion to heap\n");
   printf("    Preorder :"); preorder(T); printf("\n");
   printf("    Inorder  :"); inorder(T); printf("\n\n");

   heap2BST(T);
   printf("\n+++ After conversion to BST\n");
   printf("    Preorder :"); preorder(T); printf("\n");
   printf("    Inorder  :"); inorder(T); printf("\n\n");

   printf("+++ The final tree %s a BST\n", isBST(T,0,INFTY) ? "is" : "is not");

   exit(0);
}