Sistemas

HeapSort
Utilizando o mesmo princípio do SelectSort, o HeapSort é um algoritmo que utiliza uma estrutura de dados conhecida como Heap binário para manter o próximo item a ser selecionado [14]. Criado em 1964 por Robert W. Floyd e J.W.J. Williams, ele é um algoritmo de Ordem de Complexidade O(n log n).
Existem dois tipos de heaps: Os heaps de máximo (max heap), em que o valor de todos os nós são menores que os de seus respectivos pais; e os heaps de mínimo
(min heap), em que o valor de todos os nós são maiores que os de seus respectivos pais. Assim, em um heap de máximo, o maior valor do conjunto está na raíz da árvore, enquanto no heap de mínimo a raíz armazena o menor valor existente [3].
Os heaps podem ser representados por arranjos, nesse caso a maior(menor) chave está sempre na posição 1 do vetor.
Como foi apresentado o método HeapSort baseia-se em uma estrutura de dados.
A implementação dos algoritmos das operações necessárias ao heap e o método propriamente dito, foram apresentadas pelos Programas 2.12 e 2.13
O algoritmo procede da seguinte forma [8]:
1. Zera os valores das váriáveis de medição através do método ClearAll();
2. Inicia a contagem de tempo com a função start();
3. Constroi o heap através do método Build;
4. Troca o item na posição 1 do vetor (raiz do heap) com o item da posição n.
5. Usa o procedimento ReMake para reconstituir o heap para os itens Array[1],
Array[2], até Array[n 1].
6. Repita os passos 4 e 5 com os n 1 itens restantes, depois com os n 2, até que reste apenas um item.
27
7. A cada comparação incrementa a variável mComparations e a cada movimenta ção incrementa a variável mMoviments;
8. Pausa a contagem de tempo e calcula o tempo gasto armazenando o valor na variável mTime;
2.7.2 Estudo da Complexidade
A análise de complexidade deste algoritmo também é complexa como os dois métodos apresentados anteriormente. Porém, será apresentado resultados de testes empíricos [8].
 O procedimento ReMake