Criptografia

Heapsort Método proposto por Floyd e Williams, em 1964; É considerado um método de ordenação de bom desempenho O desempenho no pior caso é semelhante ao caso médio; É considerado uma variação do método de ordenação por seleção Faz um uso “comportado” da memória;
Heapsort
O método consiste em: Transformar a seqüência inicial em uma seqüência que esteja associada à uma estrutura do tipo heap; Heap é uma árvore binária em que a diferença máxima de altura entre os nós folha é de um nível.
Os nós do nível mais profundo são preenchidos da esquerda para a direita.
Todo nó deve armazenar uma chave maior do que as dos seus filhos;
Heapsort
Um heap pode ser representado em um vetor com índices c1, c2, ..., cn da seguinte forma: Para toda chave ci, com i entre 1 e n div 2:
• c1 é a raiz da árvore;
• c2i é a raiz da sub-árvore esquerda de ci e c2i+1 é a raiz da sub-árvore direita de ci;

Heapsort
Para um vetor com índices de 1 a 7 haveria o seguinte heap associado: C1 | C2 | C3 | C4 | C5 | C6 | C7 |

1 2 3 4 5 6 7
Para que a estrutura seja um heap, cada nó deve ter chave maior do que as chaves de seus filhos.
C1

C3
C2

C7
C6
C5
C4

A transformação começa a partir do nó que ocupa a posição n div 2 do vetor, neste caso a posição de índice 3 19 | 5 | 30 | 11 | 9 | 12 | 20 |

1 2 3 4 5 6 7
Como esta sub-árvore respeita o critério para formação do heap, volta-se para o nó associado à posição anterior do vetor.
19

|
30
5

20
12
9
11

Para que a estrutura seja um heap, cada nó deve ter chave maior do que as chaves de seus filhos. 19 | 5 | 30 | 11 | 9 | 12 | 20 |

1 2 3 4 5 6 7

Neste ponto, percebe-se que a chave 5 é menor do que a dos seus filhos,