Lista 6 Cap Tulo 6

465 palavras 2 páginas
Lista 6 – Análise e projeto de algoritmos
Aluno : 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,

Relacionados

  • Administradora
    1558 palavras | 7 páginas
  • METODOLOGIA PARA FAZER UM RELAT RIO 2012
    2244 palavras | 9 páginas
  • Python
    26033 palavras | 105 páginas
  • Qualquer
    26010 palavras | 105 páginas
  • trabalho
    9247 palavras | 37 páginas
  • Cartilha de segurança da internet
    53501 palavras | 215 páginas
  • prova
    3514 palavras | 15 páginas
  • apostila Latex
    19287 palavras | 78 páginas
  • A politica na cidade
    9458 palavras | 38 páginas
  • Gestão do Conhecimento
    16937 palavras | 68 páginas