/* This is the solution for question 1 of 2000 exam */
#include <stdio.h>
#include <math.h>
int i,ii,n,t,k;
int a[100000],y,z;
int even(x)
int x;
{if((x/2)*2==x)return 1; else return 0;}
swap(i,j)
int i,j;
{int t; t=a[i]; a[i]=a[j]; a[j]=t;}
siftup(p,q)
  int p, q; 
{
  int j, k, m, r;
  y=a[p]; k=1;
  z=a[p]; j=p+1; if(p==0) r=n; else r=p;
  m=p; 
  while (even(r)&&(j<=q)) { /* m is location of the minimum */
	if (a[j]<z){z=a[j]; m=j;}
	j=j+k; k=2*k; r=r/2;
  }
//  if (p<m) { swap(p,m); if (even(m)) siftup(m,q); }
  if (z<y) { swap(p,m); if (even(m)) siftup(m,q); }
}
heap(n)
  int n;
{ int w;
  for (i=n-2; i>=0; i=i-2) {
    siftup(i,n);
  }
//  for (ii=0;ii<=n-1;ii++)printf("%d ",a[ii]); printf("\n");
  for (i=n-1; i>=1; i--) {
    swap(0,i);
    siftup(0,i-1);
  }
}
main()
{ printf("input size \n");
  scanf("%d",&n); 
  for (i=0;i<=n-1;i++) a[i]=rand()%100;
  for (i=0;i<=n-1;i++) printf("%d ", a[i]); printf("\n");
  t=clock();
  heap(n);
  for (i=0;i<=10;i++) printf("%d ",a[i]);
  printf("\n");
  printf("time= %d millisec\n",(clock()-t)/1000);
}