HeapSort - Método de Ordenação

O HeapSort também conhecido como método de ordenação por arvores é baseado no método de seleção direta. Este algoritmo utiliza uma estrutura de dados chamada de heap, que consiste em uma arvore cuja raiz é o elemento de menor valor, caso seja um heap de mínimo, ou o de maior valor, caso seja um heap de máximo. Com o heap construído o HeapSort apenas cria o heap a partir do vetor de entrada, e o algoritmo apenas vai removendo do heap e colocando no vetor de saída.
A heap pode ser representada como uma árvore ou como um vetor, sendo ordenada de forma crescente e decrescente, desta forma, com a ordenação crescente deve ser construído um heap máximo (o maior elemento fica na raiz) onde A[i/2] >=A[i ] (ou seja, pai >= filho) (representação como árvore). Com a ordenação decrescente, deve ser construído um heap mínimo (o menor elemento fica na A [i/2] <=A [i ] (ou seja, pai <= filho) (representação como vetor).
Vantagens: O comportamento do Heapsort é sempre O(n log n), qualquer que seja a entrada. Não necessita de nenhuma memória adicional. E bom para arquivos com grandes registros. Desvantagens: O Heapsort não é recomendado para vetores de entrada com poucos elementos, devido a complexidade do heap; O Heapsort não é estável. O anel interno do algoritmo é bastante complexo se comparado com o do Quicksort.

A figura mostra um vetor pq[1..55]. Os números dentro das caixas são os índices. O número de elementos em cada camada, exceto talvez no último, é uma potência de 2.  O pai de cada elemento na camada i está na camada i-1. O número de camadas é a parte inteira de 1+lg(55),  sendo lg(x) o piso de log2x.  Se eu tivesse N no lugar de 55, o número de camadas seria 1+lg(N).