Heaps: Algoritmos e Estruturas de Dados

Prévia do material em texto

Introdução
Operações
Fila de prioridade
Algoritmos e Estruturas de Dados 2
Unidade 2: heaps
Rafael Beserra Gomes
Universidade Federal do Rio Grande do Norte
Material compilado em 17 de junho de 2014.
Licença desta apresentação:
http://creativecommons.org/licenses/
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição e Propriedades
Nó de uma árvore binária
Um nó de uma heap contém: chave, filho esquerdo e filho direito.
pai
ch
e d
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição e Propriedades
Propriedades de uma heap
30
26
18
5 7
16
8 6
28
17
4 2
19
Cada nó é maior que seus filhos (heap máximo)
ou é menor que seus filhos (heap mínimo)
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
max-heapify
build-max-heap
Operação max-heapify
10
26
18
5 7
16
8 6
28
17
4 2
19
Considere que a operação é realizada neste nó
e as sub-árvores são heaps máximos.
sub-árvore esquerda é heap máximo sub-árvore direita é heap máximo
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
max-heapify
build-max-heap
Operação max-heapify
10
26
18
5 7
16
8 6
28
17
4 2
19
Este nó é trocado pelo maior dos filhos,
caso seja menor que esse filho.
sub-árvore esquerda é heap máximo sub-árvore direita é heap máximo
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
max-heapify
build-max-heap
Operação max-heapify
28
26
18
5 7
16
8 6
10
17
4 2
19
Nesse exemplo, a sub-árvore direita
deixa de ser heap máximo.
Solução recursiva é aplicada.
sub-árvore esquerda é heap máximo
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
max-heapify
build-max-heap
Operação build-max-heap
5 7 18 6 28 8 16
5
7
6 28
18
8 16
Esta operação transforma toda a árvore binária
em um heap máximo utilizando
o procedimento max-heapify.
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
max-heapify
build-max-heap
Operação build-max-heap
5 7 18 6 28 8 16
5
7
6 28
18
8 16
A operação começa pelo penúltimo
nível (por quê?).
Nó a nó até a raiz aplica-se max-heapify.
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
max-heapify
build-max-heap
Operação build-max-heap
5 28 18 6 7 8 16
5
28
6 7
18
8 16
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
max-heapify
build-max-heap
Operação build-max-heap
28 7 18 6 5 8 16
28
7
6 5
18
8 16
A complexidade desse algoritmo é O(n) [Cormen]
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição
Extração
Incremento de chave
Fila de prioridade
Uma fila de prioridade é uma estrutura de dados que contém um conjunto de chaves,
e admite as operações:
– obter/extrair o elemento de maior/menor chave do conjunto
– incremento/decremento de uma chave específica.
A implementação mais comum é através do uso de heaps.
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição
Extração
Incremento de chave
Extração
30
26
18
5 7
16
8 6
28
17
4
19
Este nó é trocado pelo último elemento do heap.
extração
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição
Extração
Incremento de chave
Extração
4
26
18
5 7
16
8 6
28
17 19
Em seguida, aplica-se max-heapify na raiz.
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição
Extração
Incremento de chave
Incremento de chave
30
26
18
5 7
16
8 6
28
17
4 2
19
O incremento de chave é feito através
de sucessivas trocas entre filho
e pai enquanto necessário para manter a heap.
Exemplo, incrementar este nó para 29.
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição
Extração
Incremento de chave
Incremento de chave
30
26
18
5 7
16
8 6
28
17
29 2
19
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição
Extração
Incremento de chave
Incremento de chave
30
26
18
5 7
16
8 6
28
29
17 2
19
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
Introdução
Operações
Fila de prioridade
Definição
Extração
Incremento de chave
Incremento de chave
30
26
18
5 7
16
8 6
29
28
17 2
19
Rafael Beserra Gomes Algoritmos e Estruturas de Dados 2
	Introdução
	Definição e Propriedades
	Operações
	max-heapify
	build-max-heap
	Fila de prioridade
	Definição
	Extração
	Incremento de chave