equacoes diferenciais

HeapSort
• HeapSort também é um método de seleção
– ordena através de sucessivas seleções do elemento correto a ser posicionado em um segmento ordenado
• O HeapSort utiliza um heap binário para manter o próximo elemento a ser selecionado – heap binário: árvore binária mantida na forma de vetor
– o heap é gerado e mantido no próprio vetor a ser ordenado (no segmento não-ordenado)
2
Heap Binário - Exemplo
4 9 2 1 5 6 8
4
9 2
1 5 6 8
1 2 3 4 5 6 7
• raiz da árvore: primeira posição do vetor
• filhos de um nodo na posição i: posições 2i e 2i + 1
• pai de um nodo na posição i: posição ëi / 2û
Heap Binário Máximo
9 5 8 1 4 6 2
9
5 8
1 4 6 2
1 2 3 4 5 6 7
• Heap Binário tal que um nodo pai tem valor maior ou igual ao valor dos nodos filhos
3
HeapSort - Funcionamento
1. Transformação do vetor em um heap binário máximo (Construção do Heap)
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
– após cada seleção de elemento, o heap deve ser reorganizado para continuar sendo um heap binário máximo
HeapSort - Exemplo
9 5 8 1 4 6 2
1 2 3 4 5 6 7
4 9 2 1 5 6 8
1 2 3 4 5 6 7 construção do heap 9
5 8
1 4 6 2 ordenação (1a iteração)
2 5 8 1 4 6 9
1 2 3 4 5 6 7 reorganização do heap (1a iteração)
8 5 6 1 4 2 9
1 2 3 4 5 6 7
. . .
2
5 8
1 4 6
8
5 6
1 4 2
4
HeapSort – Construção do Heap
• Cria-se uma árvore binária com os elementos do vetor desordenado
• Transforma a árvore binária em um heap binário máximo
– a transformação ocorre de forma bottom-up
• inicia-se a partir dos nodos folha e vai executando a transformação em direção a raiz
Construção do Heap - Exemplo
4 9 2 1 5 6 8
1 2 3 4 5 6 7
4
9 2
1 5 6 8 inicia pelo nodo 2 (ën/2û) 4
9 2
1 5 6 8 troca com o filho de maior valor
4
9 8
1 5 6 2 próximo: nodo 9 4
9 8
1 5 6 2
(não é necessária a troca) próximo: nodo 4
9
4 8
1 5 6 2 nova troca é necessária
9
5 8
1 4 6 2