Criação de Heaps

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
Heaps
Katia S. Guimarães
katia@cin.ufpe.br
katia@cin.ufpe.br
*
*
*
Busca por Prioridade
Até agora nós estudamos estruturas de
busca através de chaves.
E se o nosso argumento de busca for diferente?
Se nós quisermos recuperar, por exemplo, 
o elemento que tem a maior chave?
katia@cin.ufpe.br
*
*
*
Estrutura Heap
 Heap é uma estrutura de prioridades, 
 na forma de árvore binária semi-completa, 
 que representa uma ordem parcial entre 
 os elementos do conjunto.
Ex:
89
9
21
22
26
34
41
74
8
15
32
4
katia@cin.ufpe.br
*
*
*
Estrutura Heap
Ex:
89
9
21
22
26
34
41
74
8
15
32
4
Implementação usual: Array unidimensional,
onde a raiz ocupa a posição 1, e os elementos
obedecem à relação: esq.i = 2i, dir.i = 2i + 1.
74
32
89
22
41
15
4
21
9
34
26
8
katia@cin.ufpe.br
*
*
*
Construção de um Heap
A construção é feita a partir do array com
os elementos desordenados, e pode ser 
feita “bottom-up” ou “top-down”. 
Na construção bottom-up, o controle segue 
das folhas à raiz (ou seja, da direita para a 
esquerda no array), construindo um heap 
único a partir de dois heaps menores + um 
novo elemento. 
katia@cin.ufpe.br
*
*
*
Construindo um Heap Bottom-up
Base: Se n = 1, então a árvore é uma folha,
não há o que fazer (a árvore já é um heap).
21
21
9
34
Ex:
Ex:
Ex:
9
34
katia@cin.ufpe.br
*
*
*
Construindo um Heap Bottom-up
Passo: Se n > 1, então usando a Hipótese 
de Indução, só é necessário ajustar a ordem
parcial com relação ao novo elemento.
21
9
34
Ex:
9
21
34
9
21
34
21
9
34

katia@cin.ufpe.br
*
*
*
Heapify
 9
9
21
22
26
34
41
74
Toma: Dois (sub)heaps + um novo elemento 
Gera:  um novo heap contendo todos.
Ex.
74
22
41
21
9
34
26
74
22
41
21
9
34
26
22
21
74
26
34
41

katia@cin.ufpe.br
*
*
*
Heapify
 9
9
21
22
26
34
41
74
Só precisamos encontrar um local apropriado para o elemento nesta nova raiz.
74
22
41
21
9
34
26
74
22
41
21
9
34
26
22
21
74
26
34
41

katia@cin.ufpe.br
*
*
*
Algoritmo Heapify
Algoritmo Heapify(i )
 Enquanto i  int (n/2) /* i tem filhos*/ faça {
 Se i < (n/2) /* i tem dois filhos*/ então
 Se A[2i ] > A[2i +1] então
 			 maior  2i 
 senão maior  2i +1
 senão /* O único é o maior*/ maior  2i ;
 Se A[i ] < A[maior] então
 { A[i ]  A[maior]; i  maior } 
 senão i  n /* deixe o laço*/ 
 }
katia@cin.ufpe.br
*
*
*
Heapify
9
21
22
26
34
41
74
21
 9
22
21
74
26
34
41

74
22
21
26
34
41
 9
 9
74
26
34
41

22
i=1
i=2
i=5
i=7
katia@cin.ufpe.br
*
*
*
Construindo um Heap Bottom-up
Algoritmo Constrói-Heap:
	 Para i  int (n/2) até 1 faça 
		Heapify
74
21
22
26
41
34
 9
74
21
22
26
34
41
 9
74
22
41
21
9
34
26
74
22
41
21
9
34
26

katia@cin.ufpe.br
*
*
*
Construindo um Heap Bottom-up

74
21
22
26
34
41
 9
74
22
41
21
9
34
26
22
21
74
26
34
41
 9
74
22
41
21
9
34
26
katia@cin.ufpe.br
*
*
*
Construindo um Heap Bottom-up

 9
21
22
26
34
41
74
74
22
41
21
9
34
26
22
21
74
26
34
41
 9
74
22
41
21
9
34
26
katia@cin.ufpe.br
*
*
*
Construindo um Heap Bottom-up
Algoritmo Constrói-Heap:
	 Para i  n/2 até 1 faça 
		Heapify (A, n, i)
Custo para construir um heap:
 T(n) = n / 2 · log (n) = O (n · log (n)) 
 Será que este custo é exato?
katia@cin.ufpe.br
*
*
*
Custo para construir um Heap Bottom-up
A cada execução da rotina Heapify o
número de comparações é no máximo 
o dobro da altura da sub-árvore que 
está sendo transformada em heap.
Logo, no total queremos a soma das 
alturas de todas as sub-árvores dentro 
de uma árvore de altura h: 
 H(h) = 2 · H(h-1) + h
katia@cin.ufpe.br
*
*
*
Custo para construir um Heap Bottom-up
A soma das alturas de todas as sub-árvores 
dentro de uma árvore de altura h é dada por: 
 H(h) = 2 · H(h-1) + h
 H(0) = 0
 h 0 1 2 3 4 5 6 7 ... 
H(h) 0 1 4 11 26 57 120 247 ...
 2h+1 2 4 8 16 32 64 128 256 ...
katia@cin.ufpe.br
*
*
*
Custo para construir um Heap Bottom-up
A soma das alturas de todas as sub-árvores 
dentro de uma árvore de altura h é dada por: 
 H(h) = 2 · H(h-1) + h H(0) = 0
 h 0 1 2 3 4 5 6 7 ... 
H(h) 0 1 4 11 26 57 120 247 ...
 2h+1 2 4 8 16 32 64 128 256 ...
 H(h) = 2h+1 - (h+2) = O (n) 
katia@cin.ufpe.br