// supondo um heap de máximo
// também é possível implementar com um heap de mínimo
// mas neste caso precisamos de um vetor auxiliar

void insereHeap(int x, int v[], int *n); // executa em O(log n) passos

int removeHeap (int v[], int *n); // executa em O(log n) passos

void heapSort (int v[], int n) {
	int i, aux;
	
	i = 0;
	while(i < n)
		insereHeap(v[i+1], v, &i);
	
	i = n;
	while (i >= 1)
		aux = removeHeap(v, &i);
		v[i+1] = aux;
}

Invariantes do segundo laço:

 - v[i+1 .. n] está em ordem crescente
 
 - v[1 .. i] é um heap de máximo
 
 - v[k] <= v[j] para 1<=k<=i e i<j<=n


Eficiência:

 - cada laço executa O(n) vezes
 
 - as operaçoes dentro do laço custam O(log n)
 
 - Portanto, o algoritmo executa em O(n log n) passos