Heapsort

FATEC DE PRAIA GRANDE
ANÁLISE E DESENVOLVIMENTO DE SISTEMAS

ESTRUTURA DE DADOS

HEAPSORT

ITAY JESUS DE SENA FILHO
JAQUELINI APARECIDA DOS SANTOS LIMA
MARCELA MORAIS
WELLINGTON ALVES ROSENDO

PRAIA GRANDE
MARÇO/2013
1. INTRODUÇÃO
Os algoritmos de ordenação ou classificação constituem uma classe de algoritmos extremamente estudada e muito popular. Em diversas aplicações as ordenações de uma das etapas, dentre muitas outras a serem efetuadas, de modo que selecionar o melhor algoritmo de ordenação é extremamente importante nestes casos.
Em busca de índices previamente ordenados, por exemplo, é a maneira mais eficiente de busca por um elemento qualquer de uma coleção.
O 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. 2. METODOLOGIA
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.

3.1 FUNCIONAMENTO
• Transformação do vetor em um heap binário:

• Estrutura do heap completa:

3.2 ORDENAÇÃO

• A cada iteração seleciona-se o maior elemento (na raiz do heap) e o adiciona no início de um segmento ordenado:

• E assim sucessivamente:

• Após a cada seleção de elemento, o heap deve ser reorganizado para continuar sendo um heap binário máximo:

• A cada iteração seleciona o maior elemento do heap (sempre está na primeira posição) e o troca com o elemento no final do segmento não-ordenado:

• Após a troca, o novo elemento raiz do heap deve ser ajustado (deve-se chamar ajustaElemento para o nodo raiz):

• O processo termina quando o heap tiver somente 1 elemento (vetor ordenado):
Vetor ordenado : 1, 2, 3, 4, 5, 7, 8, 9, 11

3. APLICAÇÃO
Uma sequência