Fila de Prioridade  XML
Índice dos Fóruns » Java Básico
Autor Mensagem
SrFabio
JavaBaby
[Avatar]

Membro desde: 18/02/2007 13:50:41
Mensagens: 99
Localização: São Miguel, Açores (Portugal)
Offline

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
[MSN]
jingle
Virtual Machine Man

Membro desde: 04/10/2006 20:40:08
Mensagens: 642
Localização: Canoas/RS
Offline

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?

This message was edited 1 time. Last update was at 01/05/2009 12:05:03

[Email] [MSN]
SrFabio
JavaBaby
[Avatar]

Membro desde: 18/02/2007 13:50:41
Mensagens: 99
Localização: São Miguel, Açores (Portugal)
Offline

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.


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



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

* - Inserir novo item

* - Remover o item com prioridade mais elevada

* - Remover um item


* - Modificar a prioridade de um item

* - Juntar duas filas de prioridades (10 Pontos)



2) Implemente o Algoritmo de Heapsort (10 Pontos)


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

This message was edited 2 times. Last update was at 01/05/2009 11:48:51

[MSN]
lavh
GUJ Master

Membro desde: 30/07/2006 16:09:55
Mensagens: 1311
Offline

SrFabio wrote: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.

This message was edited 1 time. Last update was at 01/05/2009 12:04:51

jingle
Virtual Machine Man

Membro desde: 04/10/2006 20:40:08
Mensagens: 642
Localização: Canoas/RS
Offline

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.

This message was edited 1 time. Last update was at 01/05/2009 12:04:18

[Email] [MSN]
SrFabio
JavaBaby
[Avatar]

Membro desde: 18/02/2007 13:50:41
Mensagens: 99
Localização: São Miguel, Açores (Portugal)
Offline

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
[MSN]
Mak
Debugger

Membro desde: 22/10/2008 22:13:38
Mensagens: 68
Offline

Outra coisa, é correcto remover um item que está no meio de uma fila? isso não é contra as regras de uma fila?


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 ...
[MSN]
Bruno Laturner
GUJ Expert
[Avatar]
Membro desde: 18/02/2008 16:17:53
Mensagens: 3300
Offline

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.

A resposta acima foi achada em menos de 5 minutos no google.
The prisoner falls in love with his chains. --E.W. Dijkstra
[WWW]
SrFabio
JavaBaby
[Avatar]

Membro desde: 18/02/2007 13:50:41
Mensagens: 99
Localização: São Miguel, Açores (Portugal)
Offline

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!
[MSN]
lavh
GUJ Master

Membro desde: 30/07/2006 16:09:55
Mensagens: 1311
Offline

SrFabio wrote: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.
fringos bringos
Entusiasta Java

Membro desde: 31/10/2008 00:26:29
Mensagens: 23
Offline

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.
lavh
GUJ Master

Membro desde: 30/07/2006 16:09:55
Mensagens: 1311
Offline

fringos bringos wrote: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!
Lavieri
GUJ Master
[Avatar]

Membro desde: 27/01/2004 13:39:31
Mensagens: 1851
Localização: João Pessoa / PB
Offline


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

This message was edited 2 times. Last update was at 02/05/2009 01:35:05


Sun Certified Java Programmer (SCJP 6)

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand."
-Martin Fowler et al, Refactoring: Improving the Design of Existing Code, 1999

Meu blog -> http://blog.tomazlavieri.com.br/
[ICQ]
 
Índice dos Fóruns » Java Básico
Ir para:   
Powered by JForum 2.1.8 © JForum Team