//Veja: https://www.ime.usp.br/~pf/algoritmos/aulas/hpsrt.html


#define troca (A, B) { int t = A; A = B; B = t; }

// Recebe um vetor v, com índice inicial 1
// que é um heap, exceto pela posição p,
// e rearranja o vetor de modo a
// transformá-lo em heap.
void fixUp (int p, int v[]) {
   while (p > 1 && v[p/2] < v[p]) {  
      troca (v[p/2], v[p]);          
      p /= 2;                        
   }
}

// Recebe um vetor v[1..m] que é um heap
// exceto talvez pelos índices 2 e 3 e
// rearranja o vetor de modo a
// transformá-lo em heap.
void fixDown (int m, int v[]) {
   int f = 2;
   while (f <= m) {
      if (f < m && v[f] < v[f+1])  ++f;
      // f é o filho mais valioso de f/2
      if (v[f/2] >= v[f]) break;
      troca (v[f/2], v[f]);
      f *= 2;
   }
}

// Rearranja um vetor v[1..m] de modo a
// transformá-lo em heap.
void constroiHeap (int m, int v[]) {
   int k; 
   for (k = 1; k < m; ++k) {                   
      // v[1..k] é um heap
      int f = k+1;
      while (f > 1 && v[f/2] < v[f]) {  
         troca (v[f/2], v[f]);          
         f /= 2;                        
      }
   }
}

// Rearranja os elementos do vetor v[1..n] 
// de modo que fiquem em ordem crescente.
void heapsort (int n, int v[]) {
   int m;
   constroiHeap (n, v);
   for (m = n; m >= 2; --m) {
      troca (v[1], v[m]);
      fixDown (m - 1, v);
   }
}