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

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)

BUILD-MAX-HEAP2 (A,n) 
   1. para i <- 2 crescendo até n faça
   2.    MAX-HEAP-INSERT (A,i-1,A[i])

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.