MAC0338  Análise de Algoritmos
Notas da prova Pessoal, eu lamento, mas ainda não tenho as notas da prova. As notas devem sair na próxima semana.

Tarefa 8

Entregue o exercício abaixo até a quarta-feira, dia 28 de abril.

EXERCÍCIO [CLRS 6-1] (contruindo um heap através de inserções)
Vimos que o algoritmo 

BUILD-MAX-HEAP (A,n) 
   1. para i <- chão(n/2) decrescendo até 1 faça
   2.    MAX-HEAPIFY (A,n,i)
constrói um max-heap em tempo linear. O algoritmo BUILD-MAX-HEAP pode ser reescrito da seguinte maneira: 
BUILD-MAX-HEAP2 (A,n) 
   1. para i <- 2 crescendo até n faça
   2.    MAX-HEAP-INSERT (A,i-1,A[i])
Eis os algoritmos MAX-HEAP-INSERT e HEAP-INCREASE-KEY: 
MAX-HEAP-INSERT (A,n,chave)

   1. n <- n+1
   2. A[n] <- -infinito
   3.    HEAP-INCREASE-KEY (A,n,chave)

HEAP-INCREASE-KEY (A,i,chave)

   1. A[i] <- chave
   2. enquanto i > 1 e A[chão(i/2)] < A[i] faça
   3.    A[i] <-> A[chão(i/2)]
   4.    i  <- chão(i/2)
  1. Os algoritmos BUILD-MAX-HEAP e BUILD-MAX-HEAP2 sempre produzem o mesmo max-heap quando aplicados a um mesmo vetor A? Prove ou de um contra-exemplo.
  2. Mostre que o consumo de tempo no pior caso do algoritmo BUILD-MAX-HEAP2 é theta(n log(n)), onde n é o número elementos do max-heap.

Last modified: Wed May 5 20:01:35 BRT 2004