GUJ Discussões   :   últimos tópicos   |   categorias   |   GUJ Respostas

Fila de Prioridade


#1

Ola gente, tenho uma questão para vos colocar que me está a fazer muita confusão. É o seguinte, tendo uma fila de prioridade faz algum sentido ter dois métodos remove? Um deles remove um item (sem critério..portanto como estamos a falar de filas deve remover o primeiro) e outro que remove o item com maior prioridade. A confusão é.. sendo uma fila de prioridade, ela vai estar ordenada de acordo com a prioridade de cada item, ou seja, o primeiro item será o que tem mais prioridade (é o primeiro a sair...), estou errado? Então para quê dois remove se eles vão sempre remover o primeiro item? Ou será que numa fila de prioridade (!= Fila) se pode remover elementos do meio? As regras não são as mesmas que uma Fila normal?

Agradecia qualquer tipo de ajuda


#2

Procurei na Net ainda antes de te responder só para da uma confirmada...
E não achei motivo nenhum para ter dois remove, até mesmo fui atraz de exemplo feito em java , e nenhum que vi tinha dois remove.

onde foi que você viu que era preciso dois remove?


#3

Pois, então a minha confusão tem razão de ser. No enunciado de um trabalho o professor manda fazer dois remove. Vou colocar aqui o enunciado, mas antes que me interpretem mal, NÃO QUERO QUE ME FAÇAM O TRABALHO DE CASA. Quero apenas esclarecer esta dúvida ou ter alguma dica para que eu o possa fazer sozinho.

Ele apenas colocou isto..acho que se esqueceu de dar alguns detalhes, não?


#4

Faz sentido ter dois remove.

O primeiro remove é este trivial que você falou, de remover o item com maior prioridade.

O segundo é remover um item que pode estar em qlq posição, e depois disso ter que reorganizar a fila(o que pode não ser tão fácil). Você está usando heap para implementar?

Esse segundo remove pode ser útil na seguinte situação por exemplo: Suponha que você tem uma fila de prioridade, e uma fila normal, ambas apontando para os mesmos elementos. Pode ser que um elemento seja removido na fila normal, mas ele não seja o primeiro da fila de prioridade, dai se faz necessário um método para remover um elemento em qlq posição entendeu? Para exemplificar mais:

Suponha que seja um controle áereo, a fila normal é ordenada pela ordem de chegada e a fila de prioridade pela quantidade de combustivel dos aviões que estão chegando. Concorda que um avião pode ter chegado com o tanque cheio, então a vez dele na fila normal vai chegar primeiro que na fila de prioridade, daí você vai ter que remover ele do meio da fila de prioridade.


#5

acredito que esse "remover um item" seja remover um item especifico, por exemplo você passe a prioridade/ item e ele remove o item que tem essa prioridade/item.
unica razao que econtrei pra ter esses dois remove.


#6

Ou seja, terei de ter sempre em conta os dois tipos de fila? Porque partindo do princípio que a fila de prioridade está sempre ordenada (porque quando chamar o método inserir ou remover vou sempre reordenar a fila) quando quiser remover o item com maior prioridade ele vai estar sempre na primeira posição. Outra coisa, é correcto remover um item que está no meio de uma fila? isso não é contra as regras de uma fila? É que se eu puder remover items do meio da fila então a minha dúvida fica já esclarecida. O que li sobre as filas é que têm um método que insere um item no fim da fila, e um que remove o elemento do inicio da fila (First in First Out) ..se por acaso for remover um item com prioridade X que esteja no meio da fila não estarei a quebrar as regras inerentes a uma fila? É porque assim é como se tivesse a trabalhar com uma lista.

Obrigado desde já pelas ajudas..estou perto de esclarecer as minhas dúvidas :smile:


#7

Então, lendo o tópico eu sempre tive a sensação q, no contexto, fila == lista ... e o q não pode ter itens "do meio" removidos são as pilhas ... sendo assim, no caso, daria para ter um método remover por posição, passando a posição como parâmetro, nesta fila ...

Me corrijam se eu estiver errado pq tbm fiquei um pko na dúvida agora ...


#8

Se for pensar que filas são sempre FIFO, então filas de prioridade não poderiam ter esse nome. Você pode pensar que se inserir sempre itens com a mesma prioridade, aí sim ela se comportaria como FIFO.

Mas realmente não faz sentido ter dois métodos remover para FIFO que removam o primeiro elemento. De qualquer forma eu deixaria isso de lado e faria os dois, um para remover o primeiro, outro para qualquer elemento da lista. Tudo por questão de aprendizado.


#9

Pois, assim o farei. Vou fazer o remover item com maior prioridade, que é o remove que remove o primeiro da fila e farei o remove item, que remove qualquer item na fila.

Muito obrigado pela ajuda pessoal!

Cumprimentos!


#10

Fábio,

na prática, se você está trabalhando apenas com a "Fila de Prioridade" então o mais correto é que você só remova o elemento de maior prioridade, que é o primeiro, senão realmente não faz sentido ter a "Fila de Prioridade"

Mas se o seu professor pediu para remover qlq um, o que você pode fazer? :smile: Tem que implementar.

Na verdade ele tá pedindo isso mais pelo desafio do exercício, já que você vai ter que remover um elemento de qualquer posição da lista, e vai ter que reordenar a sua lista novamente por causa disso, isso se você estiver usando Heap, que é uma forma eficiente de implementar filas de prioridade.

Mas eu concordo que se um dia vc fosse fazer uma fila dessas no emprego, tvz não teria o método pra remover de qlq lugar, a menos que precise, como no exemplo do avião que eu dei.


#11

O que eu consigo pensar é tipo em uma fila de supermercado onde idosos., gestantes... estão na fila e tem prioridade, e alguem simplesmente resolve desistir de continuar naquela fila e sai.


#12

Tbm! É um bom exemplo!


#13

ja existe uma classe que faz isso em Java... o nome dela é PriorityQueue => http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

desde que o comparator que vc use, para criar a classe, use propriedades que possam ser alteradas, em um objeto, e assim possa modifcar sua posição de prioridade de saida, para atender ao item 1.5 da lista...

1.1 => PriorityQueue(Collection<? extends E> c) suporta isso
1.2 => add(E e) suporta isso
1.3 => poll() faz isso
1.4 => remove(Object o) remove um item especifico, não a partir de um index, mas seu professor não foi especifico quanto a isso.
1.5 => se ao criar o PrioertyQueue, vc definir um comparator, com propriedades de seus itens que possam ser alteradas, a ordem de prioridade de um item pode ser alterada
1.6 => addAll(Collection<? extends E> c) suporta isso, e pode receber portanto outra fila no parametro, juntando assim as duas files...

enfim essa classe que seu professor quer ja existe na API do java, não sei c ele ker q vc a implemente do ZERO, mas mesmoa ssim, o código fonte dessa classe é livre

boa sorte

........

Edit.: se mesmo assim, houver a exigencia de remover um item de indice especifico da lista, é simples...

/**
 * Remove o item de indice "index" da lsita de prioridade
 * @return se removeu ou não o item da lista
 */
public boolean remove(PriorityQueue pq, int index) { x
       if (index >= pq.size() || index < 0)
           return false;
       int count = 0;
       for(Object o : pq)
          if (count++ == index)
              return pq.remove(o);
       return false; //nunca chega aqui, já que index < pq.size(), vai com certeza remover algum item antes
}

#14