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))

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