O algoritmo HeapSort é um algoritmo de ordenação por seleção que foi desenvolvido por Robert W. Floyd e J.W.J. Williams em 1964.
Nascido em Nova York, Robert W. Floyd concluiu o ensino médio aos 14 anos. Com 17 anos, concluiu o curso de bacharelado em artes liberais na Universidade de Chicago e em 1958 recebeu o título de Bacharel em física. Em 1950 tornou-se membro da equipe da Fundação de Pesquisa Armour (hoje Instituto de Pesquisa IIT) no Illinois Institute of Technology. A partir da década de 60, iniciou uma longa jornada de publicações de muitos trabalhos notáveis, dentre esses, o desenvolvimento do algoritmo de ordenação HeapSort.
Uma versão inicial do HeapSort foi publicada por Robert W. Floyd em 1962 sob o nome Treesort. Dois anos mais tarde, J.W.J. Williams publicou uma versão melhorada sob o nome HeapSort. E em dezembro de 1964, Robert W. Floyd publicou uma versão final com o nome Treesort 3.
O HeapSort utiliza uma estrutura de dados chamada Heap para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, sendo essencial que a propriedade max-heap seja mantida. Essa propriedade garante que o valor de todos os nós são menores que os de seus respectivos pais.
A Heap pode ser representada como uma árvore(árvore binária com propriedades especiais) ou como um vetor. Veja essas duas representações nas imagem a seguir:
Na abordagem em que a Heap é um vetor, podemos resumir o funcionamento do algoritmo utilizando a seguinte estratégia:
1. Selecione o menor item do vetor.
2. Troque-o com o item da primeira posição do vetor.
3. Repita estas operações com os (n – 1) itens restantes, depois com os (n – 2) itens, e assim sucessivamente.
O HeapSort é um dos algoritmos com melhor desempenho e é bastante utilizado em sistemas operacionais no gerenciamento de memória e na promoção de filas de prioridade, pois possui desempenho em tempo de execução satisfatório em sequências aleatoriamente desordenadas, utiliza pouca memória e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio, isso porque possui complexidade O(n lg n). Com isso, torna-se uma ótima possibilidade de utilização, visto que muitos dos algoritmos de ordenação possuem desempenho insatisfatório no pior cenário, quer em tempo de execução, quer no uso de memória, como por exemplo, os algoritmos Bubble Sort e Selection Sort que possuem ordem de complexidade O(n²).
Uma forma mais divertida de ver o funcionamento do algoritmo é através do vídeo abaixo que mostra uma dança baseada nas regras desse algoritmo de ordenação onde é possível verificar a formação da Heap e o funcionamendo do HeapSort:
Referências:
Grupo PET Computação UFCG, 2013. All rights reserved.
