Lista de discuss�o de MAC 2301
[Pr�via por Data][Pr�xima por Data]
[Pr�via por Assunto][Pr�xima por Assunto]
[�ndice por Data][�ndice por Assunto]
[Envie uma nova mensagem para a lista]
[Responda esta mensagem]
EP2: Maldidos O(log(n))
- Subject: EP2: Maldidos O(log(n))
- From: Thomas Ufer <phx@ozdobe.org>
- Date: Wed, 22 May 2002 00:20:51 -0300
Socorro,
como eu retiro um processo da fila de impressao em tempo O(log(n))?!?
No caso de haver um processo com tempo maior que 10 min ate rola:
se a Heap for constituido de apontadores para os no's da lista por ordem de
ingresso, eh soh apagar esse no' e remover o primerio item do heap. Mas mesmo ai
ja encrenca um pouco. Tendo removido o primeiro (maior prioridade/tempo) do heap
como eu reordeno ele? No material de aula
(http://www.ime.usp.br/~gold/cursos/2002/mac2301/aulas/aula6.txt) soh tem o
"prototipo" da funcao pra fazer isso: RemoveMax(C). Na aula isso foi falado mas
eu nao lembro como faz.
Mas se eu tiver que retirar o primeiro da lista ligada (por ordem de ingresso)?
Como eu fasso uma busca no Heap em tempo O(log(n))?
Pensei em fazer uma busca, pelo tempo, comecando pela raiz e fazer uma rotina
recursiva que vai percorrendo o Heap (arvore binaria) indo de pai para filho (e
eventualmente subindo novamente de nivel, se passar do elemento procurado) ate
achar.Soh que o tempo de pior caso dessa busca vai ser da ordem "n". A media vai
ser O(log(n))?
Aceito sugestoes...
[]'s
Thomas