#include <stdio.h>
int a[10]={6,2,8,10,5,1,7,3,4,9};

void insertheap(int t, int l, int h) {
  int large;

  large=2*l+1; /* left side */
  while (large <= h) {
    if ((large < h) && (a[large] < a[large+1])) large++;
    if (t>=a[large]) break;
    else {
      a[l]=a[large]; l=large; large=2*l+1;
    }
  }
  a[l]=t;
}

void buildheap() {
  int l;

  for (l=10/2-1; l >=0; l--) {
    insertheap(a[l],l,9);
  }
}

void heapsort() {
  int i,t;

  buildheap();
  for (i=9; i>=1; i--) {
    t=a[i];
    a[i]=a[0];
    insertheap(t,0,i-1);
  }
}

void main() {
 int i,j;

 clrscr();
 printf("original order --> \n");
 for (i=0; i<10; i++) printf("%2d ",a[i]); printf("\n");

 heapsort();
 printf("sorted order --> \n");
 for (i=0; i<10; i++) printf("%2d ",a[i]); printf("\n");
}