Também tive uma dúvida sobre heap, mas essa é simples. Para montar um heap precisa de tempo O
Aquele algoritmo melhorado da última aula pra achar fecho convexo precisa ordenar os vértices, mas não ficou claro o porquê ou se só utilizar a pilha já acha um fecho convexo.
Também tive uma dúvida sobre heap, mas essa é simples. Para montar um heap precisa de tempo O
, mas algoritmos de ordenação baseados em comparação não tem tempo mínimo O(n logn)?
Também tive uma dúvida sobre heap, mas essa é simples. Para montar um heap precisa de tempo O
Sobre o algoritmo de Grahan para cálculo de fecho convexo. Se eu não ordenar os pontos pelo ângulo formado um ponto poderá entrar na pilha e não sair mais, dando resultado errado. Se vocês quiserem dar uma olhada no algoritmo com mais cuidado, a página na wikipedia está bem feita:
http://en.wikipedia.org/wiki/Graham_scan
Montar um heap custa O. Para ordenar o vetor precisamos algo como:
void heapsort (vetor v[], int n)
{
elemento aux;
montaheap (v, n);
for (m = n; m > 1; m--){
aux = v[m-1];
v[m-1] = v[0];
v[0] = aux;
rebaixa (v, m-1, 0);
}
Certo?
--
carlinhos
http://en.wikipedia.org/wiki/Graham_scan
Montar um heap custa O
void heapsort (vetor v[], int n)
{
elemento aux;
montaheap (v, n);
for (m = n; m > 1; m--){
aux = v[m-1];
v[m-1] = v[0];
v[0] = aux;
rebaixa (v, m-1, 0);
}
Certo?
--
carlinhos