HeapSort é uma técnica de ordenação baseada em comparações com base na estrutura de dados Heap Binária. É semelhante ao tipo de seleção onde encontra-se o maior elemento e o coloca na última posição, depois repetimos o mesmo processo para os elementos restantes.
O que é Binary Heap?
Definimos como árvore binária completa. Uma árvore binária completa é uma árvore binária, em que todos os níveis, exceto possivelmente o último, está completamente cheio, e todos os nós estão, tanto à esquerda quanto a direita, completos.
A Heap Binária é uma árvore binária completa onde os itens são armazenados em uma ordem especial de tal modo que o valor de um nó pai é maior (ou menor) do que os valores nos seus dois nós filhos. O primeiro é chamado de heap max e este último é chamado min heap.
A árvore Heap pode ser facilmente representada em um vetor, uma vez que ela é uma árvore binária completa. Se o nó pai é armazenado no índice i, o filho esquerdo pode ser calculada por 2 * i + 1 e filho direito por 2 * I + 2 (assumindo que a indexação começa em 0).
Os passos da ordenação pelo HeapSort:
- Construir uma Heap Máxima a partir dos dados de entrada.
- Nesta altura, o maior item é armazenado na raiz do heap e em seguida será substituído pelo último item da pilha, seguido por redução do tamanho da pilha por 1. Em seguida reestruturamos a árvore.
- Repita os passos acima até que o tamanho da pilha seja 1.
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.
Assista ao slide abaixo para ter informações completas sobre HeapSort.
Todas as informações sobre o tema estão contidas no slide.
Link: http://salveasuaempresa.com.brheapsort.html
Veja no Deck: http://slides.com/francielesena/heapsort
It’s actually a great and useful piece of info.
I am satisfied that you simply shared this useful
info with us. Please keep us up to date like this. Thank you
for sharing.