SEMINÁRIO DE ALGORITMOS
“ ÁRVORES E HEAPS “
Daniel Mascarenhas Alheiros
Ronald José da Silva Santiago
“ ÁRVORES E HEAPS “
Introdução
• Linearidade de Filas e Pilhas
• Árvores (definição e propriedades)
• Heaps
• Operações em Heaps
• Conclusão
Comentário sobre Filas e Pilhas
São Estruturas Abstratas de
dados ou seja, implementam uma
gama de operações pré-definidas.
Push
Pop
ÁRVORES
“São estruturas de dados onde existe
uma hierarquia, o que exige uma maior
elaboração estrutural em relação às listas,
filas e pilhas.”
ÁRVORES
DEFINIÇÕES
1. Nó ou Vértice
2. Aresta
3. Raiz
4. Folha
5. Pai
6. Filho
7. Descendente
8. Altura
9. Grau
Exemplo:
ÁRVORES
DEFINIÇÕES
1. Nó ou Vértice
2. Aresta
3. Raiz
4. Folha
5. Pai
6. Filho
7. Descendente
8. Altura
9. Grau
Exemplo:
ÁRVORES
DEFINIÇÕES
1. Nó ou Vértice
2. Aresta
3. Raiz
4. Folha
5. Pai
6. Filho
7. Descendente
8. Altura
9. Grau
Exemplo:
ÁRVORES
As árvores não
têm ciclos, isto é,
existe apenas um
único caminho entre
dois nós quaisquer
contidos nelas.
a
b
c
d
ÁRVORES
Formas de Representação:
1. Implícita: Utiliza arrays (vetores);
a
b
c
d
h
A= a
g
f
e
i
b
c
d
e
f
g h
i
ÁRVORES
Formas de Representação:
1. Implícita: Utiliza arrays (vetores);
A= a
b
c
d
e
f
g h
i
O primeiro termo do array é a raiz da árvore, o
segundo é o seu filho à esquerda e o terceiro, o
seu filho à direita, e assim sucessivamente.
Podemos então perceber uma fórmula genérica
para encontrar os filhos de um elemento: os filhos
de A[i] são A[2i] e A[2i+1].
ÁRVORES
Formas de Representação:
2. Explícita: Utiliza os nós como registros
com um campo de dados e dois campos de
apontadores.
A
B
D
H
C
E
I
F
nó=
G
dado
L R
HEAPS
São árvores binárias cujas
obedecem à seguinte propriedade:
chaves
“ A chave de todo nó é maior ou igual às
chaves dos seus descendentes. ”
9
8
7
4
6
5
2
3
1
HEAPS
Têm grande utilidade na implementação
de filas de prioridade, que são tipos
abstratos de dados definidos por duas
operações: Insere(x) e Remove(r), onde r é
sempre a raiz.
9
8
7
4
6
5
2
3
1
HEAPS
Remoção:
1. Sempre na raiz, pois é o elemento de
maior prioridade. E agora, o que fazer com
o que resta do heap (dois heaps
separados)?
?
Passo
1
8
7
4
6
5
2
3
1
HEAPS
Remoção:
2. Neste ponto a raiz recebe o último
elemento do que era o antigo heap.
2
Passo
2
7
4
8
6
5
3
1
HEAPS
Remoção:
3. Agora deve-se comparar a nova raiz com
seus filhos a fim de que se mantenha a
Propriedade de Heap.
2
Passo
3
7
4
8
6
5
3
1
HEAPS
Remoção:
4. Como o filho à esquerda era o maior dos
filhos analisados (8 e 6) e também era
maior que o seu antecessor (2), trocam-se
as posições.
8
Passo
4
7
4
2
6
5
3
1
HEAPS
Remoção:
5. Enquanto existirem antecessores menores
que os seus descendentes, repete-se o
Passo 4 (neste exemplo troca-se o 2 pelo 7,
e depois o pelo 4).
8
Passo
4
7
4
2
6
5
3
1
HEAPS
Remoção (algoritmo implícito):
Algoritmo remoção (A, n);
Entrada: A um array de tamanho n representando um heap;
Saída: Max (o elemento máximo do heap);
início
se n=0 então imprima: “ O heap está vazio “
senão
Max:=A[1];
A[1]:=A[n];
n:=n-1; pai:=1; filho:=2;
enquanto filho <= n-1 faça
se A[filho] < A[filho+1] entao filho:=filho+1;
se A[filho] > A[pai] entao troque A[pai] por A[filho];
pai:=filho; filho:=2*filho;
senão filho:=n {para o laço}
fim.
HEAPS
Inserção:
1. É sempre realizada após o último
elemento do heap.
8
Passo
1
7
4
2
6
5
9
3
novo elemento
1
HEAPS
Inserção:
2. Verifica-se se o novo elemento está na
posição correta, isto é, se a árvore continua
sendo um heap. Em caso negativo, troca-se
ele pelo seu antecessor imediato (seu pai).
8
Passo
2
7
9
2
6
5
4
3
1
HEAPS
Inserção:
3. Enquanto houver pais menores que os
filhos, troca-se as suas posições.
9
8
7
2
6
5
4
Passo
2
3
1
HEAPS
Inserção (algoritmo implícito):
Algoritmo Inserção (A, n, x);
Entrada: A um array com n termos (heap), x um número (chave);
Saída: A (o novo heap), n (o novo tamanho do heap);
início
n:=n+1; {assumimos que não estouramos (overflow) o array}
A[n]:=x; filho:=n;
pai:= n div 2; {a variável pai recebe o resultado inteiro da divisão}
enquanto pai >= 1 faça
se A[pai] < A[filho] então
troque A[pai] e A[filho]
filho:=pai;
pai:=pai div 2;
senão pai:=0; {para parar o laço}
fim.
“ ÁRVORES E HEAPS “
Conclusão
• Filas e Pilhas (Facilidade X Limitação)
• Árvores
•Formas Implícita X Explícita
• Heaps
•Utilizações X Limitações
FIM