ordenacao heapsort
2340 palavras
10 páginas
HeapSortEstrutura de Dados II
Jairo Francisco de Souza
HeapSort
Algoritmo criado por John Williams (1964)
Complexidade O(NlogN) no pior e médio caso
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. HeapSort
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. HeapSort
Exemplo de um heap:
HeapSort
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.
HeapSort
Tenta-se evitar a utilização real de uma árvore.
A idéia é utilizar a abordagem de heap representando uma árvore como um array:
HeapSort
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