Fila de Prioridade

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?

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?

SrFabio:

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

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.

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.

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

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 …

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.

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!

SrFabio:

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

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

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.

Tbm! É um bom exemplo!

1) Implemente uma fila de prioridade com todas as seguintes funcionalidades:

1.1 - Criar fila, a partir de um conjunto de items

1.2 - Inserir novo item

1.3 - Remover o item com prioridade mais elevada

1.4 - Remover um item

1.5 - Modificar a prioridade de um item

1.6 - Juntar duas filas de prioridades (10 Pontos)

2) Implemente o Algoritmo de Heapsort (10 Pontos)

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
}