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]

Re: EP2: Maldidos O(log(n))



  Thomas,

  Para resolver o problema do tempo 0, vc poderia guardar na estrutura de
cada processo o índice dele no heap. Desse modo ao retirar o 1o.
elemento da fila dupla, vc não tem que percorrer o heap, uma vez
que vc já tem o índice.
  Abaixo segue uma função para retirada de um elemento de um heap, em
pseudo-linguagem:
void removeheap(int pai) //pai é a posição de retirada

i)comparar o último elemento (heap[nelem]) com os filhos da posição pai,
que são heap[2*pai] e heap[2*pai+1]
ii)se pelo menos um dos filhos tiver maior prioridade que o pai, copiar o
filho com maior prioridade para a posição pai (heap[pai]=heap[2*pai], por
exemplo)
iii)atualizar o índice pai para o índice do filho que fez a troca, no
exemplo anterior: pai=2*pai
iv)repetir as etapas ii) e iii) até que o último elemento tenha mais
prioridades que os filhos, ou pai chegue a (nelem/)2 +1 (não há mais
filhos)
v)finalmente, copiar o último elemento para a posição pai
(heap[pai]=heap[nelem]) e atualizar o número de elemento (nelem--)

Obs: se vc resolveu guardar os índices do heap na estrutura dos processos,
não se esqueça de atualizar a informação a cada troca efetuada.
Obs2: essa é só pra lembrar que para retirar o elemento de maior
prioridade basta passar pai=1 , como parâmetro da função.

   Espero ter ajudado,

   Victor


On Wed, 22 May 2002, Thomas Ufer wrote:

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