11_Heap binaria

Prévia do material em texto

1
Heap binária
1
Estrutura de Dados e 
Algoritmos
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Heap Binária
2
� É uma árvore binária satisfazendo duas 
propriedades:
1. Shape property
� Estar completa até pelo menos seu penúltimo nível
� Se o seu último nível não estiver completo, todos os 
nós do último nível deverão estar agrupados à 
esquerda
2. Tipo de Heap
� Max heap: 
� o valor de todos os nós é menor do que o nó pai. 
� A raiz possui o maior elemento
� Min heap: 
� o valor de todos os nós é maior do que o nó pai. 
� A raiz possui o menor elemento
2
Heap Binária (Exemplo)
3
� Applet
� http://people.ksp.sk/~kuko/bak/index.html 
completa
esq→dir
max heap
Árvore 
binária
completa
40
19 36
17 3 25 1
2 7
Heap Binária (Representacao)
4
Como árvore binária Como array
3
Exercício 1
5
� Desenhe a Max heap representada pelo vetor a 
seguir
Posição
Valor
Exercício 2
6
� A árvore binária a seguir pode representar uma max
heap? Justifique.
42
32
2 1
6
17 7
5 4 3 8
4
Exercício 3
7
� Qual o número mínimo de elementos de uma heap 
com altura h?
40
19 36
17 3 25 1
2
h
20+21+...2h-1 + 1 = n
(1 + 2 + 4 + ... 2h-1) + 1 = n
1(2h - 1)/1 +1 = n
2h - 1 +1 = n
2h = n
Exercício 4
8
� Qual o número máximo de elementos de uma heap
com altura h?
40
19 36
17 3 25 1
h
20+21+...2h = n
2h+1 - 1 = n
5
Exercício 5
9
� Qual a altura de uma heap em função do número de 
elementos?
� Vendo os casos extremos (2h e 2h+1-1)
2h ≤ n ≤ 2h+1-1 
h ≤ lg n ≤ h +1
h = �lg(n)�
Heap Binária
10
� Qual o invariante de uma Max heap?
� Como descrever o invariante de uma Max heap de 
maneira formal?
� Como manter o invariante de uma Max heap? 
� Quão custoso é manter o invariante?
6
Heap Binária
11
� Qual o invariante de uma Max heap?
� Todo elemento pai é maior que seus elementos filhos
� Como descrever o invariante de uma Max heap de 
maneira formal?
� A[Parent(i)] ≥ A[i], para todo i que não é raiz
� Como manter o invariante de uma Max heap? 
� A cada inserção e remoção, trocar elementos de forma a 
validar a propriedade
� Quão custoso é manter o invariante?
� Os elementos vão subindo ou descendo na heap => 
O(log n)
Heap Binária (Heapify)
12
Heapify: 
Processo de consertar uma heap para que 
ela preserve seus invariantes
7
Heap Binária (Heapify)
13
Heap Binária (Heapify)
14
8
Exercício
15
� Ilustre a operação Heapify considerando o seguinte
array:
Exercício
16
� O que acontece com o Heapify quando o elemento
A[i] é maior que seus filhos?
9
Exercício
17
� Qual a análise do pior caso da Heapify?
� O pior caso ocorre quando a árvore é dividida em 2/3
� T(n) = T(2n/3) + O(1)
� Caso 2. Θ(log n)
42
32
2 1
6
17 12
5 4 3 8
2n/3
Heap Binária
18
� Como construir uma Heap a partir de um array 
qualquer?
� Qual o custo dessa construção?
Por que não n?
10
Exercício
19
� Utilize o build heap para construir a heap a partir do 
vetor <04,01,03,02,16,09,10,14,08,07>.
Exercício
20
� Utilize o build heap para construir a heap a partir do 
vetor <04,01,03,02,16,09,10,14,08,07>.
11
Exercício
21
� Utilize o build heap para construir a heap a partir do 
vetor <04,01,03,14,16,09,10,02,08,07>.
Exercício
22
� Utilize o build heap para construir a heap a partir do 
vetor <04,01,10,14,16,09,03,02,08,07>.
12
Exercício
23
� Utilize o build heap para construir a heap a partir do 
vetor <04,16,10,14,07,09,03,02,08,01>.
Exercício
24
� Utilize o build heap para construir a heap a partir do 
vetor <16,14,10,08,07,09,03,02,04,01>.
13
Build Heap (Análise)
25
� Qual a ordem de complexidade do Buildheap?
� Aproximação inicial: O(n.log n) 
� Cálculo simples mas não é limite restrito (tight)
� Análise mais detalhada indica: Θ(n). Observe que heapify 
varia de acordo com a altura do nó (a maioria dos nós 
tem uma altura pequena).
Heap Binária
26
� E se a Heap já estiver construída? Como funcionam
as inserções e remoções na mesma?
14
Heap Binária (Inserções)
27
� Insira o elemento na última posição da heap.
� Mantenha o invariante da heap, considerando o 
novo elemento inserido.
40
19 36
17 3 25 1
2 7 20
40
19 36
17 3 25 1
2 7
40
20 36
17 19 25 1
2 7 3
40
19 36
17 20 25 1
2 7 3
inserir(20)
Viola invariante
Viola invariante Invariante ok
Exercício
28
� Insira os elementos 32, 45, 17, 2, 5 na heap
seguinte. Mostre visualmente como a heap fica após 
cada operação.
40
19 36
17 3 25 1
2 7
15
Heap Binária (Inserção)
29
� Como seria o algoritmo de inserção na Heap?
� Qual a diferença básica entre esse algoritmo e o 
Heapify?
� Qual a complexidade do algoritmo?
Heap Binária (Remoções)
30
� Remoções na heap acontecem sempre pelo
elemento raiz (elemento máximo ou mínimo).
� Mova o último elemento para a raiz
� Mantenha o invariante.
40
19 36
17 3 25 1
2 7
Remover maximo
Viola invariante
Viola invariante Invariante ok
7
19 36
17 3 25 1
2
36
19 7
17 3 25 1
2
36
19 25
17 3 7 1
2
16
Exercício
31
� Aplique remover máximo 4 vezes e mostre 
visualmente como a heap fica após cada operação
40
19 36
17 3 25 1
2 7
Heap Binária (Remoção)
32
� Como seria o algoritmo de remoção na Heap?
17
Heap Binária (Remoção)
33
� Como seria o algoritmo de remoção na Heap?
� Qual a complexidade do algoritmo?
Heap Binária
34
� Heaps são estruturas eficientes para
armazenamento?
� É possível usar heaps para ordenar um conjunto de 
dados?
� Abordagens para o Heapsort:
1. Pega o conjunto de dados e vai inserindo em uma Min 
heap. Depois é só remover da heap na ordem
crescente (Abordagem 1)
2. Ordenar no próprio vetor (Abordagem 2 / in-place)
18
Heapsort (Abordagem 1)
35
4 1
4
1
2 3
4 16 9 10
1
4 3
1
4 3
2
1
2 3
4
Inserir(4) Inserir(1) Inserir(3) Inserir(2)
1
2 3
4 16
Inserir(16)
1
2 3
4 16 9
Inserir(9) Inserir(10)
Heapsort (Abordagem 1)
36
Inserir(14)
1
2 3
4 16 9 10
14 8
1
2 3
4 16 9 10
14
Inserir(8)
8
1
2 3
4 7 9 10
14
Inserir(7)
16
19
Heapsort (Abordagem 1)
37
Inserir(14)
1
2 3
4 16 9 10
14 8
1
2 3
4 16 9 10
14
Inserir(8)
8
1
2 3
4 7 9 10
14
Inserir(7)
16
Depois disso é só remover todos os elementos da heap e eles
estarão em ordem!
Heapsort (Abordagem 2)
38
� Recebe um array completo e transforma-o em heap
de forma in-place.
� Evita uso de memória extra.
20
Heapsort (Abordagem 2)
39
� Considerando uma Max heap.
Faça a análise!
Heapsort (Abordagem 2)
40
21
Heapsort (Abordagem 2)
41
Exercício
42
� Use o heapsort (abordagens 1 e 2) para ordenar o 
vetor <4,1,3,2,16,9,10,14,8,7>. 
22
Características
43
� Não é stable
� In place (Abordagem 2)
� Pior caso e caso médio similares
� Θ(n.log n)
� Uma boa implementação do quicksort é melhor
� Heapsort é tão bom quanto Mergesort e Quicksort
(exceto para o pior caso)
� Entretanto, a estrutura tem uma enorme utilidade
Priority Queues
44
� Uma fila de prioridades é uma estrutura de dados 
para manter um conjunto S de elementos, cada um 
com uma chave associada, em determinada ordem
� Maior chave deve estabelecer a ordem de acesso aos
elementos.
23
Priority Queues
45
� Operações necessárias:
� Inserir(chave) – insere um novo elemento
� Maximo() – retorna o elemento com maior chave
� Extract_max() – remove o elemento com maior chave
retornando-oem seguida.
A heap permite essas operações?
Priority Queues
46
� Implementação em Java
� PriorityQueue
� Min heap genérica
� Elementos comparáveis ou trabalha com um Comparator
� Mudança de prioridade on the fly violam a propriedade da heap
� Implementar uma max-heap precisa apenas “inverter” o 
Comparator usado.
24
Heap (Implementação)
47
� Como implementar uma heap que guarda elementos
contendo uma chave e dados satélites?
� Elementos devem ser objetos comparáveis (menor, 
maior, igual)
� Ou a heap deve trabalhar com um Comparator (mais
incomum, mais reutilizável)
� Como considerar isso na interface da heap?
Heap (Implementação)
48
public interface GenericHeap<T extends Comparable<T>> {
public boolean isEmpty();
public void insert(T element);
public T extractRootElement();
public T rootElement();
public T[] heapsort(T[] array);
public void buidHeap(T[] array);
public T[] toArray();
}
25
Referências
49
� Capítulo 7