void swap(double &x, double &y){
//ARG:
//DESC: The values stored in x and y are exchanged.
  double tmp = x;
  x = y;
  y = tmp;
}

void heapify(double a[], int i, int n){
//ARG: 0 <= i <= n = length(a); a[2i..n-1] contains
//     heaps rooted at 2i and 2i+1
//DESC: a[i..n-1] contains heap rooted at i
  for(int k = 2*i; k < n; i = k, k = 2*i){
    if(k+1 < n && a[k] < a[k+1]) k++;
    if(a[i] < a[k])
      swap(a[i], a[k]);
    else return;
  }
}

void heapSort(double a[], int n){
//ARG: n = length(a)
//DESC: a[0..n-1] is increasingly sorted.
  // Building a heap.
  for(int i = n/2; 1 <= i; i--)
    heapify(a, i, n);
  // Sorting
  for(int i = n; 1 < i; i--){
    swap(a[1], a[i]);
    heapify(a, 1, i-1);
  }
}