Slides de Aula III

Prévia do material em texto

Prof. MSc. Olavo Ito
UNIDADE III
Estruturas de Dados
 A recursividade é a possibilidade de uma função se chamar ou, então, voltar a ser chamada 
após a execução de funções que ela mesma chamou. 
 A cada chamada, o programa abre um novo espaço na memória para a sua execução. 
 A cada chamada recursiva, é guardada uma cópia dos parâmetros de modo que não 
percamos os valores dos parâmetros das chamadas anteriores. 
As funções recursivas têm duas características importantes: 
 Ponto de parada: geralmente, um limite superior ou inferior da 
regra geral; 
 Regra geral: reduz a resolução do problema por meio da 
invocação recursiva de casos menores, resolvidos mediante à 
resolução de casos ainda menores e, assim, sucessivamente, 
até atingir o ponto de parada, que finaliza o método. 
Recursividade
int main(){
.
.
.
funrec(x)
Recursividade
função funrec(param)
se <ponto de parada alcançada?>
retorne retorno
senão
funrec(param)
retorne retorno
fimse
Regra 
Geral
Regra 
Geral
int main(){
.
.
.
funrec(x)
Recursividade
função funrec(param)
se <ponto de parada alcançada?>
senão
funrec(param)
retorne retorno
fimse
não
Regra 
Geral
função funrec(param)
se <ponto de parada alcançada?>
senão
funrec(param)
retorne retorno
retorne retorno
fimse
Regra 
Geral
Regra 
Geral
int main(){
.
.
.
funrec(x)
Recursividade
função funrec(param)
se <ponto de parada alcançada?>
não
senão
funrec(param)
retorne retorno
fimse
Regra 
Geral
Regra 
Geral
Regra 
Geral
Regra 
Geral
função funrec(param)
se <ponto de parada alcançada?>
não
senão
funrec(param)
retorne retorno
fimse
função funrec(param)
se <ponto de parada alcançada?>
senão
retorne retorno
funrec(param)
retorne retorno
fimse
int main(){
.
.
.
funrec(x)
Recursividade
se <ponto de parada alcançada?>
função funrec(param)
não
senão
funrec(param)
retorne retorno
fimse
Regra 
Geral
função funrec(param)
se <ponto de parada alcançada?>
não
senão
funrec(param)
retorne retorno
fimse
Regra 
Geral
função funrec(param)
se <ponto de parada alcançada?>
senão
retorne retorno
funrec(param)
retorne retorno
fimse
sim
Regra 
Geral
Regra 
Geral
int main(){
.
.
.
funrec(x)
Recursividade
se <ponto de parada alcançada?>
função funrec(param)
não
senão
funrec(param)
retorne retorno
fimse
função funrec(param)
senão
retorne retorno
fimse
se <ponto de parada alcançada?>
funrec(param)
Regra 
Geral
Regra 
Geral
retorne retorno
int main(){
.
.
.
funrec(x)
Recursividade
função funrec(param)
senão
retorne retorno
fimse
se <ponto de parada alcançada?>
funrec(param)
retorne retorno
Regra 
Geral
Regra 
Geral
Estrutura multidimensional:
 O nó aponta para mais nós 
além do próximo.
Árvores
Verificar I/O
Verificar 
swap
Verificar % 
CPU
PROBLEMA 
NA RAM
I/O
PROBLEMA NO 
APLICATIVO
PROBLEMA 
NO CPU
IN
V
E
S
T
IG
A
R
ALTO BAIXO ALTO BAIXO
ALTO BAIXO
 As árvores são estruturas de dados 
multidimensionais que permite a 
representação de hierarquias ou a 
representação em vários níveis. 
 Uma árvore é composta por um conjunto de 
nós, que podem, ou não, ter ramificações. 
 Existe um nó denominado raiz, que pode 
ramificar (ou não) em subárvores, cujas 
raízes são ligadas, diretamente, a essa raiz 
e, assim, sucessivamente. 
Árvores: definições e representações básicas 
Nós externos 
ou folhas
Nós internos
Sub-
árvore
Sub-
árvore
Sub-
árvore
Sub-
árvore
Sub-
árvore
Sub-
árvore
Raiz
Sub-
árvore
 Em uma árvore binária, cada nó tem zero, um ou dois filhos. 
De maneira recursiva, define-se uma árvore binária como sendo: 
 Uma árvore vazia;
 Um nó raiz com uma das subárvores, uma identificada como a subárvore da direita (sad) ou 
uma identificada como a subárvore da esquerda (sae); 
 Um nó raiz tendo duas subárvore, identificadas como a subárvore da direita (sad) e a 
subárvore da esquerda (sae). 
Árvores binárias
A
B C
D E
SAE SAD
raiz
Propriedade da altura:
Árvores binárias
Altura=0 Altura=1 Altura=2
Altura=4
Propriedade da lateralidade:
Árvores binárias
A
B B
A
 Percorrer uma árvore para buscar a informação ou, mesmo, para descrevê-la. 
 Ao percorrer uma árvore, precisamos ter um critério.
 Pré-ordem, ordem, pós-ordem. 
Percurso em árvores binárias
O percurso em ordem faz, recursivamente, a partir da raiz, o seguinte: 
 Lê o nó; 
 Vai para a SAE; 
 Vai para a SAD; 
 Retorne. 
Percurso em árvores binárias: pré-ordem
Acompanhe a evolução desta animação, conforme a videoaula
O percurso em ordem faz, recursivamente, a partir da raiz, o seguinte: 
 Vai para a SAE; 
 Lê o nó; 
 Vai para a SAD; 
 Retorne. 
Percurso em árvores binárias: ordem ou in order
Acompanhe a evolução desta animação, conforme a videoaula
O percurso em pós-ordem faz, recursivamente, a partir da raiz, o seguinte: 
 Vai para a SAE; 
 Vai para a SAD; 
 Lê o nó; 
 Retorne. 
Percurso em árvores binárias: pós-ordem
Acompanhe a evolução desta animação, conforme a videoaula
Qual das alternativas mostra a árvore a seguir em ordem?
a) 15, 7, 20, 17, 25.
b) 17, 25, 7, 20,15.
c) 25, 17, 20, 15, 7.
d) 7, 17, 25, 20, 15.
e) 7, 15, 17, 20, 25.
Interatividade
0015
0007 0020
0017 0025
Qual das alternativas mostra a árvore a seguir em ordem?
a) 15, 7, 20, 17, 25.
b) 17, 25, 7, 20,15.
c) 25, 17, 20, 15, 7.
d) 7, 17, 25, 20, 15.
e) 7, 15, 17, 20, 25.
Resposta
0015
0007 0020
0017 0025
Estrutura de um nó:
Estrutura de árvores binárias em C
sae sad
Manipulação básica:
Estrutura de árvores binárias em C
2
4
8
8
4
82
a3
a2
a1
a2
a1a3
Como fazer a busca de um valor dentro de uma estrutura?
Em uma estrutura unidimensional:
Procurar o número 2:
Árvores binárias de busca
20
50
67
8013
2
31
25 35
60
62
 Solução: utilizar uma árvore binária de busca.
 Uma árvore binária de busca ou árvore binária de pesquisa é uma estrutura de dados em 
que todos os nós da subárvore esquerda possuem um valor inferior ao do nó raiz, e todos os 
nós da subárvore direita possuem um valor superior ao do nó raiz.
Árvores binárias de busca
Acompanhe a evolução desta 
animação, conforme a videoaula
Na busca, as seguintes operações devem realizadas recursivamente, lembrando que, a cada 
movimentação, o novo nó passa a ser a raiz: 
 Se o valor procurado for igual ao da raiz, o valor será encontrado; 
 Se o valor procurado for menor do que o da raiz, deveremos buscar na SAE; 
 Se o valor procurado for maior do que o da raiz, deveremos buscar na SAD; 
 Se o nó for a folha da árvore, o valor requerido não terá sido encontrado. 
Árvores binárias de busca: busca
20
50
67
8013
2
31
25 35
60
62
20
50
67
8013
2
31
25 35
60
62
Fazer a operação de busca até encontrar uma subárvore livre ou uma folha, obedecendo aos 
seguintes critérios: 
 Se a chave a ser inserida for menor do que a chave do nó analisado, inseriremos a chave na 
subárvore esquerda; 
 Se a chave a ser inserida for maior do que a chave do nó analisado, inseriremos a chave na 
subárvore direita; 
 Se a subárvore estiver ocupada, seguiremos com a busca. 
Árvores binárias de busca: inserção
55
Árvores binárias de busca: remoção
Fazer a remoção de um nó sem comprometer a estrutura é um processo que necessita de um 
cuidado maior. Existem três situações para excluir um nó de uma árvore binária de busca: 
 Remoção na folha; 
 Remoção de um nó com um filho; 
 Remoção de um nó com dois filhos. 
Árvores binárias de busca: remoção
 Remoção na folha. 
 Remover o nó da árvore. 
2
13
20
50
67
8060
6225 35
31
Árvores binárias de busca: remoção
 Remoção de um nó com um filho. 
 Filho sobe para a posição do pai. 
2
13
20
50
67
60
62 7225 35
31 80
Árvores binárias de busca: remoção
 Remoção de um nó com dois filhos. 
Tem duas possibilidades:
 O nó a ser retirado é substituído pelo nó mais à direita da subárvore esquerda.2
13
20
31
25 35 62 72
80
67
60
50
 Remoção de um nó com dois filhos. 
Tem duas possibilidades:
 O nó a ser retirado é substituído pelo nó mais à esquerda da subárvore direita. 
Árvores binárias de busca: remoção
2
50
13
20
31
25 35
60
62 72
80
67
Busca sequencial:
Conforme visto:
Busca binária:
 A busca ou a pesquisa binária são realizadas em um vetor ordenado. 
 Verificar se o elemento que desejamos buscar é igual, menor 
ou maior do que o elemento do meio do vetor.
 Caso o valor seja menor, ignoramos o resto do vetor que seja 
maior do que este valor e buscar, somente, na metade 
“menor” do vetor. 
 Caso o valor pesquisado seja maior do que o valor do 
elemento do meio, ignoramos a metade menor, e buscar, 
somente, na metade “maior” do vetor, ou seja, a partir do 
elemento do meio. 
Pesquisa de dados: sequencial e binária
Busca binária:
Pesquisa de dados: sequencial e binária
Buscar 37 Buscar 86
Quais os valores que poderão substituir quando o valor 55 for removido?
a) 48, 75.
b) 48, 78.
c) 47, 75.
d) 47, 78.
e) 38, 75.
Interatividade
1
21
29
38
48
45
4640
47
55
75
90
81
78
98
Quais os valores que poderão substituir quando o valor 55 for removido?
a) 48, 75.
b) 48, 78.
c) 47, 75.
d) 47, 78.
e) 38, 75.
Resposta
1
21
29
38
48
45
4640
47
55
75
90
81
78
98
 A entrada é um vetor cujos elementos precisam ser ordenados. 
 A saída é o mesmo vetor com os seus elementos na ordem especificada.
Vários algoritmos:
 BubbleSort (método da bolha);
 QuickSort (método da troca e partição);
 InsertionSort (método da inserção direta);
 BinaryInsertionSort (método da inserção direta binária);
 Ordenação por seleção SelectionSort (método da 
seleção direta);
 HeapSort (método da seleção em árvore);
 MergeSort (método da intercalação);
 BucketSort (método da distribuição de chave).
Ordenação de dados
 Percorrer os dados, sequencialmente, várias vezes. 
 Os elementos são comparados com o seu sucessor. 
 Se os elementos não estiverem ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado. 
 Neste método, a ordenação acontece colocando os maiores valores no final do vetor.
Ordenação de dados: BubbleSort – Método da bolha
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado. 
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado. 
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado. 
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado. 
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado. 
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado. 
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado.
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Os elementos são comparados com o seu sucessor. Se os elementos não estiverem 
ordenados devemos trocá-los de posição. 
 O processo é repetido, seguidamente, do início até o final do vetor, até que o vetor 
fique ordenado.
Ordenação de dados: BubbleSort – Método da bolha
Acompanhe a evolução desta animação, conforme a videoaula
 Este método baseia-se na divisão do vetor em dois vetores menores, baseados em um 
elemento chamado pivô; normalmente, o primeiro elemento do vetor. 
 Um dos vetores contém os elementos menores do que o pivô enquanto que o outro contém 
os maiores. 
 O pivô é colocado entre ambos, ficando na posição média. 
 Os dois vetores são ordenados de forma idêntica, até que se chegue a um único 
vetor ordenado.
Ordenação de dados: QuickSort (método da troca e partição) 
Ordenação de dados: QuickSort (método da troca e partição) 
Acompanhe a evolução desta animação, conforme a videoaula
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
 Uma vez localizada, a célula eleita passa para o elemento seguinte do vetor. 
Ordenação de dados: InsertionSort (método da inserção direta) 
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
Ordenação de dados: InsertionSort (método da inserção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
Ordenação de dados: InsertionSort (método da inserção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
Ordenação de dados: InsertionSort (método da inserção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
Ordenação de dados: InsertionSort (método da inserção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte ea comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
Ordenação de dados: InsertionSort (método da inserção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
Ordenação de dados: InsertionSort (método da inserção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 O conteúdo da célula é eleita e comparado com o valor da célula anterior. 
 Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior. 
 Se o valor anterior for menor, ou chegou ao início, é a posição correta que a célula escolhida 
deverá ocupar. 
Ordenação de dados: InsertionSort (método da inserção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: BinaryInsertionSort (método da inserção 
direta binária)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: BinaryInsertionSort (método da inserção 
direta binária)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: BinaryInsertionSort (método da inserção 
direta binária)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: BinaryInsertionSort (método da inserção 
direta binária)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: BinaryInsertionSort (método da inserção 
direta binária)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: BinaryInsertionSort (método da inserção 
direta binária)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: SelectionSort (método da seleção direta) 
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: SelectionSort (método da seleção direta)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: SelectionSort (método da seleção direta)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: SelectionSort (método da seleção direta)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: SelectionSort (método da seleção direta)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: SelectionSort (método da seleção direta)
Acompanhe a evolução desta animação, conforme a videoaula
 Implementa uma busca binária para encontrar o local correto para colocar o elemento eleito. 
Ordenação de dados: SelectionSort (método da seleção direta)
Acompanhe a evolução desta animação, conforme a videoaula
O método de ordenação HeapSort consiste em uma árvore binária completa que obedece às 
seguintes propriedades: 
 A raiz de uma árvore com Heap Máximo é, sempre, o maior valor da estrutura; 
 Troque a posição da raiz com o último filho, (o último elemento, agora, é o nó de 
maior valor); 
 Refazer o Heap sem o último elemento, pois ele já estará posicionado. 
 O HeapSort, assim como no SelectionSort posiciona um a um 
o elemento dento do vetor; no caso, de trás para a frente, e, 
assim como no InsertionSort, utiliza-se uma técnica que evita 
percorrer o restante do vetor. 
Ordenação de dados: HeapSort (método da seleção em árvore) 
Heap: 
 Um árvore Heap é uma árvore binária em que a altura aumenta se todas folhas de um 
nível estiverem preenchidas; 
 O preenchimento é feito da esquerda para a direita. 
Heap Máximo:
 O pai é maior do que o filho.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1 5
17
19
23
7
2
11 3
13
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz. 
Ordenação de dados: HeapSort (método da seleção em árvore) 
95
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz. 
Ordenação de dados: HeapSort (método da seleção em árvore) 
6<75
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
68>52
2x2=4 esquerdo
2x2+1=5 direito
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
6<68
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
4x2=8 esquerdo
4x2+1=9 direito
55>25
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
6<55
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
68>64
1x2=2 esquerdo
1x2+1=3 direito
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
51<68
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
55>52
2x2=4 esquerdo
2x2+1=5 direito
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
51>55
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 3) Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
4x2=8 esquerdo
4x2+1=9 direito
25>6
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort(método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
64>55
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
48<64
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
3x2=6 esquerdo
3x2+1=7 direito
37>2
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
48>37
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
55>48
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
25<55
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2x2=4 esquerdo
2x2+1=5 direito
52>51
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
25<52
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
5x2=10 esquerdo
5x2+1=11 direito
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
52>48
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
6<52
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2x2=4 esquerdo
2x2+1=5 direito
51>25
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
6<51
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
4x2=8 esquerdo
4x2+1=9 direito
25>6
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
51>48
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2<51
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2x2=4 esquerdo
2x2+1=5 direito
25>6
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2<25
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
5x2=10 esquerdo
5x2+1=11 direito
25>6
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
48>25
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
37>48
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
3x2=6 esquerdo
3x2+1=7 direito
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
37>25
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2<37
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
3x2=6 esquerdo
3x2+1=7 direito
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
25>2
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz. 
Ordenação de dados: HeapSort (método da seleção em árvore) 
6<25
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2x2=4 esquerdo
2x2+1=5 direito
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
1x2=2 esquerdo
1x2+1=3 direito
6>
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
2<6
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 HeapSort. 
 Deixar em Heap Máximo.
 Remover a raiz e colocar 
o último elemento na raiz. 
 Heap fica a partir 
da raiz.
Ordenação de dados: HeapSort (método da seleção em árvore) 
 Recursivamente divide o vetor em metades, retorna juntando as partes em ordem crescente.
Ordenação de dados: MergeSort (método da intercalação) 
Acompanhe a evolução desta animação, conforme a videoaula
 BucketSort é um algoritmo de ordenação através da segmentação de um vetor em uma 
quantidade finita de baldes (buckets). Cada balde é, então, ordenado individualmente, seja 
usando um algoritmo de ordenação diferente, seja aplicando recursivamente o 
algoritmo BucketSort.
 Iniciar um vetor de baldes, inicialmente, vazio. 
 No vetor original, inserindo cada elemento em um balde. 
 Ordenar todos os baldes não vazios. 
 Colocar os elementos dos baldes que não estão vazios no vetor original. 
Ordenação de dados: BucketSort (método do balde) 
Ordenação de dados: BucketSort (método do balde) 
topo
balde
Ordenação de dados: BucketSort (método do balde) 
Acompanhe a evolução desta 
animação, conforme a videoaula
Faça a associação correta:
a) A-1, B-3, C-2.
b) A-3, B-1, C-2.
c) A-3, B-2, C-1.
d) A-1, B-2, C-2.
e) A-2, B-1, C-3.
Interatividade
A Faz a troca, 
sequencialmente, entre 
os elementos 
adjacentes trocando de 
posição, se fora 
de ordem.
1 QuickSort
B Recursivamente adota
um elemento pivot 
dividindo o vetor 
em dois.
2 SelectionSort
C A partir do primeiro 
elemento não ordenado 
e faz a troca com o 
menor valor no 
vetor restante.
3 BubbleSort
Faça a associação correta:
a) A-1, B-3, C-2.
b) A-3, B-1, C-2.
c) A-3, B-2, C-1.
d) A-1, B-2, C-2.
e) A-2, B-1, C-3.
Resposta
A Faz a troca, 
sequencialmente, entre 
os elementos 
adjacentes trocando de 
posição, se fora 
de ordem.
1 QuickSort
B Recursivamente adota
um elemento pivot 
dividindo o vetor 
em dois.
2 SelectionSort
C A partir do primeiro 
elemento não ordenado 
e faz a troca com o 
menor valor no 
vetor restante.
3 BubbleSort
 Um grafo é uma estrutura abstrata que 
representa um conjunto de elementos 
denominados de vértices, e as suas relações de 
interdependência ou arestas.
Grafos: conceitos, representação e aplicações
Aplicações:
 Diagramas de pré-requisitos; 
 Relações de amizade em 
redes sociais; 
 Mapas de rotas; 
 Circuitos elétricos; 
 Grafos de dependência 
(PERT). 
Grafos: conceitos, representação e aplicações
Fonte: autoria própria.
Fonte: Pixabay License. Disponível em: 
https://pixabay.com/vectors/network-
people-business-icon-5508173/
Fonte: Pixabay License. 
Disponível em: 
https://pixabay.com/vectors/circ
uit-board-electronics-158374/
Fonte: Jeremy Kemp em 
Wikipédia em inglês –
Transferido de en.wikipedia 
para a Wiki Commons; 
domínio público. Disponível 
em: 
https://commons.wikimedia.or
g/w/index.php?curid=1939096
t=4 mo
t=3 mo
t=1 mo t=3 mo
t=2 mo
t=3 mo
Grafo dirigido:
 As arestas são pares ordenados de vértices saindo de um em direção ao outro.
Grafo não dirigido:
 Representa uma relação simétrica (conjunto de pares não ordenados) sobre o conjunto 
de vértices. 
Tipos de grafos
 Quando uma aresta liga, diretamente, dois vértices; então, dizemos que v é adjacente a u. 
Adjacência
u
v
 Em grafos não dirigidos, o grau é determinado pela quantidade de arestas que são ligadas 
ao vértice.
 O grau de um vértice é o número de arestas que saem do vértice, mais o número de 
arestas que chegam nele. 
No caso de grafos dirigidos, há dois tipos de graus de vértice:
 Grau de saída: número de arestas que saem do vértice; 
 Grau de entrada: número de arestas que chegam ao vértice.
Grau
 Um caminho de um vértice x a um vértice y é uma sequência de vértices em que, para cada 
vértice, do primeiro ao penúltimo (pois o último não necessita do próximo), há uma aresta 
ligando esse vértice ao próximo, na sequência.
Caminho
Alguns caminhos 
válidos:
(V1, V3, V5)
(V1, V2, V3, V5)
(V4, V4, V5)
(V1, V2)
Caminhos inválidos:
(V1, V2, V3, V1)
(V4, V5, V3)
(V3, V2, V1)
(V1, V2, V3, V5, V4)
V1
V3 V5
V4
V2
 O comprimento de um caminho é o número de arestas contidas neles. 
 A contagem é feita como na altura da árvore.
Comprimento de um caminho
𝑐𝑜𝑚𝑝𝑟𝑖𝑚𝑒𝑛𝑡𝑜 𝑉1, 𝑉2, 𝑉3, 𝑉5 = 3
Caso existirem pesos associados às arestas:
Ponderação
V3
V5
V4
V2
V1
6
3
2
7
4
Matriz de adjacência:
 É uma matriz com o número de linhas e colunas correspondente à quantidade de vértices. 
Linha a linha são assinaladas aos vértices adjacentes.
Representação computacional
Matriz de adjacência:
 No caso de um grafo direcionado, nada muda com relação aos direcionados, pois, apenas, 
as adjacências são consideradas, ou seja, as arestas “chegando” não são consideradas. 
Representação computacional
Matriz de adjacência:
 Caso o grafo seja ponderado, a matriz deixa de ser binária, além do peso colocado na 
intersecção entre as vértices. 
Representação computacional
 Achar a rota mais curta entre os vértices.
 Considerar todos os vértices com a distância infinita. 
 No vértice atual, fazer o relaxamento em relação a cada aresta adjunta.
 Se a distância em relação ao vértice adjunto for menor do que o registado, atualiza-se com 
a nova menor distância.
Visto todas as adjacências, considera-se o local atual como 
encerrado, parte-se para o vértice seguinte, escolhida da 
seguinte forma:
 Se, ainda, houverem vértices abertas;
 É o vértice com a menor distância em relação à origem que 
ainda está aberto;
 Na nova vértice é registrada a informação do 
vértice anterior.
Algoritmo de Dijkstra
Algoritmo de Dijkstra
Acompanhe a evolução desta animação, conforme a videoaula
Tabela Dijkstra
Vértice dist. pai
De Até Distância Caminho
0 0 0
0 1 8 1;2;0
0 2 5 2;0
0 3 24 3;4;1;2;0
0 4 18 4;1;2;0
0 5 30 5;3;4;1;2;0
0
1
2
3
4
5
 Existe uma forma matemática de efetuar estas buscas, ela é chamada de Tabela Hash ou 
tabela de dispersão. 
 A tabela é um modo de armazenar as informações em um vetor, e, depois, procurar por 
uma informação.
 A localização é feita por meio de uma função,a função Hash.
Tabela Hash
dado função Hash resultado
Função Hash:
 É necessário para termos o acesso rápido e eficiente para avaliar a função de hash, que 
determina a posição onde o elemento se encontra armazenado na tabela;
 Espalhar bem as chaves de busca: isto é necessário para minimizarmos as ocorrências de 
colisões (veremos mais à frente), dois valores, eventualmente, sendo direcionado para a 
mesma célula da tabela. Se a função de hash resulta em muitas colisões, perdemos o 
acesso rápido aos elementos;
 Exemplo de função Hash: operação resto.
Inserção e busca
Inserção e busca
RG: 3788689
Nome: Sinfrônio
Idade: 21
RG: 15477427
Nome: Pluriana
Idade: 35
 Surgem quando duas ou mais chaves de 
busca são mapeadas para o mesmo índice 
da tabela; são chamadas de colisão.
 Uso da primeira posição consecutiva livre.
 Se a função de dispersão mapeia para 
um índice já ocupado, é procurado o 
próximo índice livre da tabela para 
armazenar o novo elemento.
Tratamento de colisão
Nome = Genécio
Idade = 27
RG função Hash resultado
Nome = Elineide
Idade = 28
RG função Hash resultado
 Uso de listas encadeadas.
 Consiste em considerar cada 
célula da Tabela Hash como o 
descritor de uma lista ligada.
Tratamento de colisão
3788689
Sinfrônio
21
324179
Genécio
27
1635034
Elineide
28
NULL
NULL
15477427
Pluriana
35
Considere a seguinte matriz de adjacência:
Qual é o grafo correspondente?
Interatividade
V0 V1 V2 V3
V0 0 1 0 0
V1 0 0 0 0
V2 0 1 0 0
V3 0 1 0 0
a) b)
c) d) 
e)
Considere a seguinte matriz de adjacência:
Qual é o grafo correspondente?
Resposta
V0 V1 V2 V3
V0 0 1 0 0
V1 0 0 0 0
V2 0 1 0 0
V3 0 1 0 0
a) b)
c) d) 
e)
ATÉ A PRÓXIMA!