// Nguyen

/* Student name: Nguyen Thaongoc */

void sort (int *a, int n)
{

void buildheap (int *a, int n);
void exchange (int *a, int i, int j);
int heapify (int *a, int i, int n);

   int i;

   buildheap(a, n);
   for (i = n - 1; i > 0; i--)
   {  
      exchange (a, 0, i); 
      heapify (a, 0, i);    
   }
}


void buildheap (int *a, int n)
{
   int i;
   for (i = n / 2 - 1; i >= 0; i--)
   heapify (a, i, n);
}


void exchange (int *a, int i, int j)
{
   int tmp;
   tmp = a[i]; 
   a[i] = a[j];
   a[j] = tmp;
}


int  heapify (int *a, int i, int n)
{
    int j;
    while (i < n/2)
    {
        j = 2 * i + 1;                        
        if ((j + 1 < n) &&  (a[j+1] > a[j]))
	    j++;       
        if (a[i] >= a[j]) 
	    return;          
        exchange(a, i, j);
        i = j;
   }
}