Heapsort

Introdução:
Heapsort é um algoritmo de ordenação que ordena localmente: apenas um número constante de elementos do arranjo é armazenado fora do arranjo de entrada em qualquer instante, assim combina os melhores atributos dos dois algoritmos de ordenação. O heapsort utiliza uma estrutura de dados chamada Heap para gerenciar informações durante a execução do algoritmo e utiliza uma estrutura arvore binária na forma de vetor para otimização do algoritmo na busca de um elemento. Um heap maximo visto como (a) uma arvore binária e (b) um arranjo. O numero dentro do circulo em cada nó na arvore é o valor armazenado nesse nó. O numero acima de um nó é o índice correspondente no arranjo. Acima e abaixo do arranjo encontramos linhas mostrando relacionamentos pai-filho; os pais estão sempre á esquerda de seus filhos. A arvore tem altura três; o nó no índice 4 (com o valor 8) tem altura um.
Tendo em vista que um heap d n elementos é baseado em uma arvore binária completa, sua altura é Θ(log n) e as operações básicas sobre heaps são executadas em um tempo maximo proporcional á altura da arvore, e assim demoram um tempo O(log n).

Estratégia:

Manutenção da propriedade de heap:
• Max-heapify é uma sub-rotina importante para a manipulação de heaps máximos. A função é deixar que o valor em A[i] “flutue para baixo” no heap máximo, de tal forma que a sub-árvore com raiz no índice i se torne um heap máximo.

Passo a passo:
1- Inicia sub rotina Max-heapify, informando o elemento que “supostamente” está infringindo as propriedades do heap máximo (A,i);
2- O elemento informado no item 1 é comparado com o valor contido no Left (i) e Right (i), a condição de comparação deste passo é importante para a operação de troca. Alem da comparação com left e right é verificada nesta comparação se left e right são menores que o tamanho do heao [A].
3- A aplicação da comparação com left e right obtém o maior valor resultante de operação, desta forma A[i] recebe o valor maior da