HEAP
ATAI
1
Heaps – Definição
Um heap é uma árvore binária T que armazena uma
colecção de chaves (ou duplos do tipo (elemento, chave))
de modo a cumprir os requisitos:
Propriedade de ordem: chave(pai)  chave(filho)
(nenhum filho possui valor menor do que seu pai)
Propriedade de estrutura: Um heap é uma árvore binária
completa. Uma árvore binária completa é uma árvore que é
completamente preenchida, com excepção dos nós folhas, que são
preenchidos da esquerda para direita.
2
Heaps
4
5
6
15
16
9
25
14
7
12
11
20
8
3
Exemplos que NÃO são heaps
4
Altura de um Heap
Um heap T com n
chaves possui uma
altura = log(n + 1)
5
Operação Inserir
Inserir a chave 6
6
Operação Inserir
1 passo: Inserir a chave na próxima posição vaga
2 passo: Subir no heap
7
Subir no heap
Trocar as chaves pai, filho que estão fora da ordem estabelecida
8
Subir no heap
9
Subir no heap


Subida no heap termina quando uma chave é maior do que a chave do
seu pai, ou chega-se ao topo do heap
(total #trocas) (h - 1), que é O(log n)
10
Operação remover

A chave do topo ao ser
removida deixa uma vaga

É necessário compor o
heap:

1 passo, por na vaga a
última chave do heap

2 passo, realizar a
operação de descer no
heap
11
Descer no heap

Descer no heap: compara o pai com o filho mais pequeno.
Se o filho é menor, troca ambos de posição
12
Descer no heap
13
Descer no heap
14
Descer no heap

Descida termina quando a chave é maior que ambos os filhos ou quando
chegar a final.
15
Implementação do Heap
public class HeapPriorityQueue implements PriorityQueue {
BinaryTree heap;
Position last;
Comparator comp;
...
}
16
Implementação do Heap

Duas maneiras de
encontrar a posição
de inserção (z) no
heap.
17
Estrutura Heap
Implementação estática: tabela 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
18