Logo Passei Direto
Buscar

Aula-heaps-1

Aula sobre listas de prioridades: definição de heap, motivação e operações (seleção, inserção, remoção, alteração). Compara implementações por lista não ordenada, lista ordenada e heap com complexidades, apresentação da árvore binária, exercícios e algoritmo de subida.

Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

Aula 28: Listas de Prioridades 
28.1
Definição de heap
Conceitos básicos 
Alteração de prioridades
Listas de Prioridades 
28.2
Motivação:
A situação acima modela uma grande quantidade
de problemas.
Os dados possuem prioridades.
A prioridade de um dado pode variar ao 
longo do tempo.
Quando desejado, deve-se selecionar o dado
de maior prioridade.
Lista de Prioridades 
28.3
É uma tabela, na qual a cada um de seus dados
está associada uma prioridade.
Em geral, a prioridade é um valor numérico. 
Também desejada a operação:
Objetivo: Descrever uma estrutura de dados que
realize as operações acima, de maneira eficiente.
alteração de prioridade de um dado
Operações básicas:
seleção do elemento de maior prioridade
inserção de um novo dado
remoção do dado de maior prioridade 
Implementação
28.4
Métodos: por
Para cada um desses métodos será avaliada a
complexidade de cada uma das seguintes
operações:
 
lista não ordenada
lista ordenada
heap
seleção (busca)
inserção
remoção
alteração
construção
28.5
Implementação por
lista não-ordenada
Os dados formam uma lista não ordenada com
n nós.
Complexidades: seleção O (n)
 inserção O (1)
 remoção O (n)
 alteração O (n)
 construção O (n)
28.6
Implementação por
lista ordenada
Os dados formam uma lista ordenada, em ordem 
decrescente de suas prioridades. As operações de 
seleção e remoção referem-se sempre ao dado de
maior prioridade. Para construir a lista, é neces-
sário ordená-la. 
Complexidades: seleção O(1)
 inserção O(n)
 remoção O(1)
 alteração O(n)
 construção O(n log n)
28.7
Implementação por heap
A chave representa a prioridade do elemento.
Os heaps formam uma estrutura conveniente para
implementar listas de prioridades.
Um heap é uma lista linear composta de
elementos com chaves s1,..., sn, satisfazendo
 si ≤ s i / 2 , 1 ≤ i ≤ n. 
Exemplo
95 60 78 39 28 66 70 33
28.8
Exercício
(i) 33 32 28 31 26 29 25 30 27 
Verifique se as seguintes listas constituem heaps. 
(ii) 33 32 28 31 29 26 25 30 27 
Tempo: 2 minutos
28.9
Solução
 i 1 2 3 4 5 6 7 8 9
 (i) si 33 32 28 31 26 29 25 30 27
 (ii) si 33 32 28 31 29 26 25 30 27
 
(i) s6>s3, não é heap. 
(ii) É heap.
28.10
Heaps e árvores binárias
Os nós de T são numerados seqüencialmente, da
raiz para os níveis mais altos, da esquerda para a
direita. 
Um heap pode ser visualizado através de uma
árvore binária completa T. 
Cada nó de T corresponde a uma chave, sendo o
rótulo do nó igual à prioridade da chave.
Os nós do último nível de T são preenchidos da
esquerda para a direita.
28.11
Heaps e árvores binárias
A propriedade si ≤ s  i / 2  do heap é equivalente a
dizer que cada nó de T possui rótulo maior ou
igual aos rótulos de seus filhos, se existirem. 
A árvore pode ser representada simplesmente
pela lista, requerendo apenas tamanho n. 
28.12
Exemplo
 i 1 2 3 4 5 6 7 8
 si 95 60 78 39 28 66 70 33 
 
95
7860
39 28 66 70
33
1
32
4 5 6 7
8
28.13
Exercício
 
Desenhar a árvore binária correspondente ao heap 
 33 32 28 31 29 26 25 30 27
Tempo: 1 minuto
 
28.14
Solução
33 32 28 31 29 26 25 30 27 
⇓
33
2832
31 29 26 25
30 27
28.15
Operações básicas em heaps
Complexidades:
 Seleção: O(1)
 Inserção: O(log n)
 Remoção: O(log n)
 Alteração: O(log n)
 Construção:O(n)
A condição si ≤ s i/2 implica que o elemento de maior
prioridade seja sempre o primeiro da ordenação, isto é,
a raiz da árvore.
Logo, a seleção pode ser realizada em O(1) passos.
28.16
Alteração de prioridades
O aumento está associado à "subida"do nó, na
árvore binária correspondente. 
Aumento ou diminuição de prioridade de um nó. 
A diminuição está associada à "descida"do nó, na
árvore binária correspondente. 
A subida e a descida de nós na árvore serão
realizadas sempre através de caminhos.
28.17
Aumento da prioridade
Exemplo: 
Aumentar prioridade do nó 6,
de 66 para 98.
95
7860
39 28 66 70
33
1
32
4 5 6 7
8
28.18
Exemplo
⇓
98
9560
39 28 78 70
33
⇓
⇓
95
7860
39 28 98 70
33
95
9860
39 28 78 70
33
28.19
Método
Seja v o nó cuja prioridade foi aumentada. Caso a
prioridade do pai de v, se existir, seja menor do
que a do v, trocar de posições v e o pai de v.
Iterativamente, repetir esta operação, tornando
v igual a seu pai, até que o nó considerado seja a
raiz da árvore, ou que sua prioridade seja menor
ou igual que a prioridade do seu pai.
 
28.20
Algoritmo de subida
Algoritmo: subir por um caminho na árvore
VoltarAnimar
procedimento subir (i)
 j :=  i/2 
 se j ≥1 então
 se T[i].chave > T[j].chave então
 T[i] ⇔ T[j]
 subir (j) 
28.21
Algoritmo de subida
O parâmetro i indica a posição do elemento a ser
revisto.
O heap está armazenado na tabela T. 
O campo chave armazena a prioridade do nó. 
A notação T[i] ⇔ T[j] indica a troca de posições em T,
entre os nós i e j.
Complexidade: Da ordem da altura da árvore.
Como a árvore é completa, complexidade O (log n).
28.22
Exercício
Seja o heap
 92 85 90 47 31 34 20 40 46 
Aplicando o algoritmo de subida, determinar o
heap resultante da alteração de prioridade do
5o. nó, de 31 por 93.
Tempo: 3 minutos
28.23
Solução
92
85 90
47 93 34 20
40 46
92
85 90
47 31 34 20
40 46
⇓
28.24
Solução
93
92 90
47 85 34 20
40 46
92
93 90
47 85 34 20
40 46
⇓
28.25
Diminuição de prioridade
Exemplo 
Diminuir a prioridade do nó 1,
de 95 por 37.
95
7860
39 28 66 70
33
28.26
Exemplo
⇓
37
60 78
39 28 66 70
33
78
60 37
30 28 60 70
33
⇓
78
60 70
38 28 60 37
33
⇓
28.27
Método
Seja v o nó cuja prioridade foi diminuída. Caso a 
prioridade de algum filho de v, se existir, seja
maior do que a de v, trocar as posições de v e seu
filho de maior prioridade. Iterativamente, repetir
esta operação, tornando v igual a seu filho de
maior prioridade, até que o nó considerado seja
uma folha, ou que sua prioridade seja maior ou
igual do que a de seus filhos. 
28.28
Algoritmo de descida
Procedimento: descer (i, n)
Algoritmo: Descer por um caminho na árvore
j : = 2 x i
se j ≤ n então
 se j < n então
 se T [j+1].chave > T [j].chave então
 j : = j+1
 se T [i].chave < T [j].chave então
 T [i] ⇔ T [j]
 descer (j, n)
28.29
Algoritmo de descida
O parâmetro i indica a posição do elemento a ser
revisto. 
O heap está armazenado na tabela T.
O campo chave armazena a prioridade do nó.
A notação T[i] ⇔ T[j] indica a troca de posição em T,
entre os nós i e j.
28.30
Exercício
Seja o heap
92 85 90 47 31 34 20 40 46 
Aplicando o algoritmo de descida, determine o
heap resultante da alteração de prioridade do
2o nó, de 85 por 15.
Tempo: 3 minutos
28.31
Solução
92
85 90
47 31 34 20
40 46
92
15 90
47 31 34 20
40 46
⇓
28.32
Solução
92
47 90
46 31 34 20
40 15
⇓
92
47 90
15 31 34 20
40 46

Mais conteúdos dessa disciplina