Lista 6 Cap Tulo 6
465 palavras
2 páginas
Lista 6 – Análise e projeto de algoritmosAluno : Gabriel Martins Leal
Matrícula : 136318
6.1-1 –
A quantidade mínima de elementos é 1, e a quantidade máxima é 2^h.
6.1-4 –
Apenas em uma de suas folhas.
6.1-7 –
Ao fazer n/2, pegamos a posição do último nó de altura h-1. Portanto somando-se um ao valor n/2, obtemos a primeira folha, e incrementando-se esse valor, a próxima folha, e assim por diante. 6.2-2 –
MIN-HEAPIFY(A, i)
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
l <- LEFT(i) r <- RIGHT(i) if l <= tamanho-do-heap[A] e A[l] > A[i] then menor <- l else menor <- i
If r <= tamanho-do-heap[A] e A[r] < A[menor]
Then menor <- r
If menor != i
Then trocar A[i] <-> A[menor]
MIN-HEAPIFY(A, menor)
6.2-5 –
MAX-HEAPIFY(A, n, i)
1. J <- 1
2. Enquanto 2j<=n faça
3.
f<-2j
4.
se f<n e A[f]<A[f+1]
5.
Então f<-f+1
6.
Se A[j]>=A[f]
7.
Então j<-n
8.
Senão troque A[j]<->A[f]
9.
J<-f
6.3-1 –
5
3
10
22
17
84
19
6
9
Começa verificando-se o 10
5
3
22
10
17
84
19
6
9
Troca 10 com 22, pois 22 é maior que 9 e 10
5
3
22
10
19
84
9
17
6
Troca 17 com 19, pois 19 é maior que 17 e 6
5
84
22
10
19
3
17
6
9
Troca 84 com 3, pois 84 é maior que 3 e 22
84
22
10
5
19
3
17
6
9
Por fim o 5 desce para o último nó, pois é menor que 84,
19 (porém 84 é maior que 19, portanto vai pro nó esquerdo) , 22, e 10.
E por fim temos o heap montado que fica :
A = (84,22,19,10,3,17,6,5,9)
6.4-2 –
O loop invariante baseia-se que o maior elemento sempre estará na primeira posição, portanto ele usa o algoritmo que transforma todos os nós em heap, e contando que todos os nós já estão de forma heap, pega o maior elemento, que no caso será o primeiro elemento do arranjo , e repete o processo sucessivamente, até que o arranjo esteja completamente ordenado. 6.4-4 –
Como o algoritmo repete n vezes um procedimento que tem complexidade lg n, cujo procedimento é transformar o arranjo em forma padrão de heap, fica óbvio que o algoritmo é no mínimo n.lg n
6.5-6 –
6.5-8 –
Podemos obter tal algoritmo,