O algoritmo heapsort

Introdução

O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção. Foi desenvolvido em 1964 por Robert W. Floyd e J.W.J. Williams.

-Principio (passos) :

Selecione o menor item do vetor

Troque-o pelo item da primeira posição

Repita operação com os elementos restantes do vetor

- Implementação direta:

Encontrar o menor elemento requer n-1 comparações

Características

-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

- Porém, além de ser mais rápido no pior caso que o QuickSort, necessita de menos memória para executar

- QuickSort necessita de um vetor O(logN) para guardar as estruturas enquanto o HeapSort não necessita de um vetor auxiliar.

-Utiliza a abordagem proposta pelo SelectionSort

-O SelectionSort pesquisa entre os n elementos o que precede todos os outros n-1 elementos

- Para ordenar em ordem ascendente, o heapsort põe o maior elemento no final do array e o segundo maior antes dele, etc.

- O heapsort começa do final do array pesquisando os maiores elementos, enquanto o selectionsort começa do início do array pesquisando os menores.

HeapSort

Para ordenar, o heapsort usa um Heap Heap é uma árvore binária com as seguintes propriedades: O valor de cada nó não é menor que os valores armazenados em cada filho. A árvore é perfeitamente balanceada e as folhas no último nível estão todas nas posições mais a esquerda.

Exemplo de um heap:

Elementos no heap não estão perfeitamente ordenados. Apenas sabe-se que o maior elemento está no nó raiz e que, para cada nó, todos os seus descendentes não são maiores que os elementos na raiz.

Por que usar um heap é importante?

-a pergunta "qual o maior elemento de vetor?" pode ser respondida instantaneamente: o maior elemento do vetor é v[1].

-se o valor de v[1] for alterado, o heap pode ser restabelecido muito rapidamente: a operação de heapfy não demora mais que lg(n) para fazer o serviço.

Algoritmo

- Dado um vetor V de n elementos, transformar o vetor em um heap

- Pegar a posição V[1] (ou seja, o maior elemento) e trocar de posição com V[max].

- Repetir o