Heap Sort: Ordenação Eficiente

Prévia do material em texto

HEAP SORT
Jefferson Henrique Barbosa Nascimento
Rodrigo do Nascimento Borges
(2020) UFPI - CCN - Dep. de Computação - Lab. de Programação (Prof. Antônio Helson).
Heap: Árvore binária quase completa;
- Vetor que emula uma organização em forma de árvore;
- Cada pai deve ser maior que seus filhos.
4 3 2 1 0
4
3 2
01
(Representação ilustrativa da organização de um vetor em forma de Heap).
- O método consiste de duas fases:
 -> Construir uma Heap de um vetor 
arbitrário ( n elementos );
-> Usar a Heap para ordenar os 
dados;
Para um elemento na posição [i] 
temos que:
PAI(i) = (i-1) / 2; (div. inteira)
FILHO_ESQUERDA(i) = 2*i+1;
FILHO_DIREITA(i) = 2*i+2.
(Relação entre os nós de um Heap).
- Primeira etapa: função cria_Heap:
8 5 6 4 7 9
0 1 2 3 4 5
- Dado n elementos;
- Colocar os números em uma árvore binária;
- Em seguida, repetir:
- Verificar se um dos filhos é maior que 
seu pai;
- Caso seja, realizar troca.(Função sendo implementada).
8 5 6 4 7 9
0 1 2 3 4 5
8
5 6
74 9
A função analisa uma 
subárvore de cada vez 
(pai com seus dois 
filhos). Faz a troca caso 
o maior dos filhos 
seja maior que seu 
pai.
8
5 6
74 9
8
7 6
54 9
8
7 9
54 6
TROCA TROCA
9
7 8
54 6
TROCA
HEAP!
Filho maior que 
o pai?? 
TROCA!
9
7 8
54 6
- Início e fim da árvore trocam de 
posição;
- Processo se repete, mas agora 
com um elemento a menos (Maior 
já está ordenado).
6 7 8 4 5 9
0 1 2 3 4 5
ORDENADO!
6
7 8
54
NOVO 
HEAP
...e por aí vai...
Novo vetor.
TROCA - Segunda etapa: (dentro da função HeapSort)