public class Heapsort
{
   public static void sort(double[] a)
   {
     double temp;
     int n = a.length;
     for(int i = n/2; i >= 1; i--)
       reHeapDown(a, i, n);
     while(n > 1)
     {
       temp = a[0]; a[0] = a[n-1]; a[n-1] = temp;
       n--;
       reHeapDown(a, 1, n);
     }
   }
   private static void reHeapDown(double[] a, int i, int n)
   {
     double root = a[i-1];
     int parent = i-1, child = 2*i;
     while(child <= n)
     {
       if(child < n && a[child+1] < a[child])
         child++;
       if(a[child-1] < root)
         break;
       a[parent-1] = a[child-1];
       a[parent] = a[child];
       a[child] = a[2*parent];
     }
     a[parent-1] = root;
   }
}