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

#define PLUS_INFTY 1000000000
#define MINUS_INFTY -1000000000

typedef struct {
   int nkey;
   int *key;
} hnode;

typedef struct {
   int p;
   int n;
   int N;
   hnode *node;
} heap;

int *geninput ( int n )
{
   int *A, i;

   A = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) A[i] = 100 + rand() % 900;
   return A;
}

void prnarray ( int *A, int n )
{
   int i;

   for (i=0; i<n; ++i) {
      printf("%-4d ", A[i]);
      if (i % 20 == 19) printf("\n");
   }
   if (i % 20) printf("\n");
}

heap initheap ( int p, int n )
{
   heap H;
   int N, i;

   H.p = p;
   H.n = 0;
   H.N = 1;

   N = (n + p - 1) / p;
   H.node = (hnode *)malloc((N+1) * sizeof(hnode));
   for (i=0; i<=N; ++i) {
      H.node[i].nkey = 0;
      H.node[i].key = (int *)malloc(p * sizeof(int));
   }

   return H;
}

void bsort ( int *A, int s )
{
   int i, j, t;

   for (j=s-1; j>0; --j) {
      for (i=0; i<j; ++i) {
         if (A[i] < A[i+1]) {
            t = A[i];
            A[i] = A[i+1];
            A[i+1] = t;
         }
      }
   }
}

void prnheap ( heap H )
{
   int i, j;

   for (i=1; i<=H.N; ++i) {
      printf("    [");
      for (j=0; j<H.node[i].nkey; ++j) printf(" %4d ", H.node[i].key[j]);
      while (j++ < H.p) printf("      ");
      printf(" ]\n");
   }
}

heap insert ( heap H, int x )
{
   int i, j, u, v, nmax, pmin, s, *K;

   K = (int *)malloc(2 * H.p * sizeof(int));
   ++(H.n);
   i = H.N = (H.n + H.p - 1) / H.p;
   H.node[i].key[H.node[i].nkey] = x;
   ++(H.node[i].nkey);
   while (1) {
      if (i == 1) break;
      j = i / 2;
      nmax = MINUS_INFTY;
      s = 0;
      for (u=0; u<H.node[i].nkey; ++u) {
         K[s++] = H.node[i].key[u];
         if (H.node[i].key[u] > nmax) nmax = H.node[i].key[u];
      }
      pmin = PLUS_INFTY;
      for (u=0; u<H.node[j].nkey; ++u) {
         K[s++] = H.node[j].key[u];
         if (H.node[j].key[u] < pmin) pmin = H.node[j].key[u];
      }
      if (pmin >= nmax) break;
      bsort(K,s);
      for (u=0; u<H.node[j].nkey; ++u) H.node[j].key[u] = K[u];
      for (v=0; v<H.node[i].nkey; ++v) H.node[i].key[v] = K[u++];
      i = j;
   }
   free(K);
   return H;
}

int getmax ( heap H )
{
   int i, rmax;

   if (H.n == 0) return MINUS_INFTY;
   rmax = MINUS_INFTY;
   for (i=0; i<H.node[1].nkey; ++i) {
      if (H.node[1].key[i] > rmax) rmax = H.node[1].key[i];
   }
   return rmax;
}

heap heapify ( heap H, int i )
{
   int l, r, c, u, v, s;
   int nmin, lmax, rmax;
   int *K;

   K = (int *)malloc(2 * H.p * sizeof(int));
   while (1) {
      l = 2*i; r = 2*i + 1;
      if (l > H.N) break;
      nmin = PLUS_INFTY;
      for (u=0; u<H.node[i].nkey; ++u) {
         if (H.node[i].key[u] < nmin) nmin = H.node[i].key[u];
      }
      lmax = MINUS_INFTY;
      for (u=0; u<H.node[l].nkey; ++u) {
         if (H.node[l].key[u] > lmax) lmax = H.node[l].key[u];
      }
      rmax = MINUS_INFTY;
      if (r <= H.N) {
         for (u=0; u<H.node[r].nkey; ++u) {
            if (H.node[r].key[u] > rmax) rmax = H.node[r].key[u];
         }
      }
      if ((nmin >= lmax) && (nmin >= rmax)) break;
      c = (lmax >= rmax) ? l : r;
      s = 0;
      for (u=0; u<H.node[i].nkey; ++u) K[s++] = H.node[i].key[u];
      for (u=0; u<H.node[c].nkey; ++u) K[s++] = H.node[c].key[u];
      bsort(K,s);
      for (u=0; u<H.node[i].nkey; ++u) H.node[i].key[u] = K[u];
      for (v=0; v<H.node[c].nkey; ++v) H.node[c].key[v] = K[u++];
      i = c;
   }
   free(K);
   return H;
}

heap delmax ( heap H )
{
   int i;

   if (H.n == 0) {
      fprintf(stderr, "*** delmax from empty heap\n");
      return H;
   }
   bsort(H.node[1].key, H.node[1].nkey);
   for (i=0; i<H.node[1].nkey-1; ++i) H.node[1].key[i] = H.node[1].key[i+1];
   if (H.N == 1) {
      --(H.node[1].nkey);
      --(H.n);
      H.N = (H.n + H.p - 1) / H.p;
      return H;
   }
   bsort(H.node[H.N].key, H.node[H.N].nkey);
   H.node[1].key[H.node[1].nkey-1] = H.node[H.N].key[H.node[H.N].nkey-1];
   --(H.node[H.N].nkey);
   --(H.n);
   H.N = (H.n + H.p - 1) / H.p;
   H = heapify(H,1);
   return H;
}

int main ( int argc, char *argv[] )
{
   int p, n, i;
   int *A;
   heap H;

   srand((unsigned int)time(NULL));

   if (argc >= 3) {
      p = atoi(argv[1]);
      n = atoi(argv[2]);
   } else {
      p = 4;
      n = 100;
   }

   printf("%d\n%d\n", p, n);

   A = geninput(n); prnarray(A,n);
   
   H = initheap(p,n);

   for (i=0; i<n; ++i) H = insert(H, A[i]);
   printf("\n+++ %d insertions made\n", n);
   prnheap(H);

   for (i=n-1; i>=0; --i) {
      A[i] = getmax(H);
      H = delmax(H);
   }
   printf("\n+++ %d deletions made\n", n);

   printf("\n+++ Input array sorted\n");
   prnarray(A,n);

   exit(0);
}