Heaps
Katia S. Guimarães
[email protected]
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?
[email protected]
2
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.
89
Ex:
74
32
22
21
41
9
34
15
26
4
8
[email protected]
3
Estrutura Heap
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.
Ex:
89
74
32
22
41
15
4
21
9
34
26
8
89
74
32
22
21
41
9
34
15
26
4
8
[email protected]
4
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.
[email protected]
5
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).
Ex:
21
21
Ex:
9
9
[email protected]
Ex:
34
34
6
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.
Ex:
21
9
34
9

21
9
34
34
34
9
[email protected]
21
21
7
Heapify
Toma: Dois (sub)heaps + um novo elemento 
Gera:
 um novo heap contendo todos.
Ex.
9
74
41
21
22
34
26
9
22
21
34
9
34
22
21
26
[email protected]
26
74
41
22
41

74
21
74
41
9
34
26
8
Heapify
9
74
41
21
22
34
26
9
22
21
34
9
34
22
26
26
74
41
22
41

74
21
74
21
41
9
34
26
Só precisamos encontrar um local apropriado
para o elemento nesta nova raiz.
[email protected]
9
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*/
}
[email protected]
10
Heapify
i=1
9

74
21
9
34
21
26
74

41
i=5
9
41
22
i=7
22
21
i=2
41
22
74
34
26
26
74
22
21
[email protected]
34
41
9
34
26
11
Construindo um Heap Bottom-up
Algoritmo Constrói-Heap:
Para i  int (n/2) até 1 faça
Heapify
9
22
34
21
74
41
26
9
22
41
21
9

34
74
34
26
9
22
21
74
41
26
[email protected]
22
21
41
74
34
26
12
Construindo um Heap Bottom-up
9
22
41
21
74
34
26
9
74
41
21
9
41
74
34
26
9
22
21
22
34
74
26

[email protected]
21
41
22
34
26
13
Construindo um Heap Bottom-up
9
74
41
21
22
34
9
74
22
21
34
9
22
26
21
[email protected]
34
26
74
41
22
41

74
21
26
41
9
34
26
14
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?
[email protected]
15
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
[email protected]
16
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
H(h) 0 1
2
4
3
11
4
26
2h+1 2
8
16
32 64
4
[email protected]
5
57
6
7 ...
120 247 ...
128
256 ...
17
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
H(h) 0 1
2
4
2h+1 2
8 16 32 64
4
3
11
4
26
5
57
6
7 ...
120 247 ...
128
256 ...
H(h) = 2h+1 - (h+2) = O (n)
[email protected]
18