Estruturas de Dados - Heap (Guilherme)

Prévia do material em texto

Estruturas de Dados
Heap
Guilherme N. Ramos
gnramos@cic.unb.br
Departamento de Cieˆncia da Computac¸a˜o
Universidade de Bras´ılia
gnramos (CIC/UnB) ED 1/4
Heap
Estrutura de dados abstrata, derivada da a´rvore, que satisfaz a
propriedade:
- Se B e´ filho de A, enta˜o B.chave ≤ A.chave (heap de ma´ximo)
- Se B e´ filho de A, enta˜o B.chave ≥ A.chave (heap de m´ınimo)
- Pode ser constru´ıda em tempo linear.
100
19
17
2 7
3
36
25 1
Na˜o ha´ restric¸o˜es quanto ao nu´mero de filhos por no´.
- Na pra´tica: 2
gnramos (CIC/UnB) ED - Heap 2/4
Aplicac¸o˜es
- E´ a estrutura de dados mais eficiente para implementar uma fila de
prioridade.
- Heapsort: algoritmo de ordenac¸a˜o in-place, complexidade
O(n·log(n)).
- Vantagem: O comportamento e´ logar´ıtmico, qualquer que seja a
entrada.
- Desvantagem: na˜o e´ esta´vel; o caso me´dio e´ pior que o do quicksort e
a implementac¸a˜o mais complexa.
- Recomendado para aplicac¸o˜es que na˜o podem tolerar um caso
desfavora´vel.
- Algoritmos de selec¸a˜o (custo linear ou mesmo constante):
- Busca de ma´ximo/m´ınimo.
- Busca do valor me´dio
- Busca do k-e´simo ma´ximo elemento
- Algoritmos de grafos (ex: algoritmo de Dijkstra)
gnramos (CIC/UnB) ED - Heap 3/4
Aplicac¸o˜es
Operac¸o˜es comuns:
- busca-max: encontra o ma´ximo item (ou busca-min)
- remove-max: remove a raiz
- insere: insere um novo valor
- fusa˜o: une duas heaps (como uma heap)
Implementac¸a˜o mais simples/eficiente
([semi-]completa): vetor
i
2i + 1 2i + 2
∀i = 0, 1, ..., n/2
100 19 36 17 3 25 1 2 7
0 1 2 3 4 5 6 7 8
gnramos (CIC/UnB) ED - Heap 4/4
	Heap
	Aplicações