O HeapSort é um método de ordenação no qual os elementos são ordenados segundo suas posições numa heap. Nele, os dados são colocados de forma desordenada em um vetor, que os organiza em forma de heap; depois disso, a raiz (o maior elemento com o uso da heap máxima ou o menor com o uso da heap mínima) é colocada no final do vetor e a estrutura é rebalanceada até que todos os elementos estejam completamente ordenados. A ordem final pode ser crescente ou decrescente (usando heap máxima ou heap mínima, respectivamente).
O custo de operação é a soma do custo de ordenação da heap [O(logn) no pior caso] com o de reordenação da mesma a cada troca da raiz com o ultimo nó (o mesmo, só que realizado n-1 vezes). Assim, o custo total de tempo é O(n*logn) no pior caso.
O heapsort não é um algoritmo de ordenação estável. Porém, é possível adaptar a estrutura a ser ordenada de forma a tornar a ordenação estável. Cada elemento da estrutura adaptada deve ficar no formato de um par (elemento original, índice original). Assim, caso dois elementos sejam iguais, o desempate ocorrerá pelo índice na estrutura original.
ResponderExcluirEste comentário foi removido pelo autor.
ResponderExcluirEste comentário foi removido pelo autor.
ResponderExcluirVantagem do HeapSort em relação ao QuickSort: No pior caso além de ser mais rápido também consome menos memória.
ResponderExcluirUma vantagem do QuickSort em relação ao HeapSort estaria no fato de que mesmo tendo a mesma complexidade no caso médio que o
QuickSort, o HeapSort acaba sendo mais lento que algumas
boas implementações do QuickSort.
Vale ressaltar que:
ResponderExcluir- O heapsort nao é recomendado para arquivos com poucos registros devido ao tempo necessario para construção do heap.
-Tem aplicações em SOs, em que usam filas de prioridades nas quais as chaves representam o tempo em que eventos devem ocorrer ; e em Sistemas de gerenciamento de memória,aonde existe a tecnica de substituir páginas menos utilizada na memória principal por uma nova página.