Classificação PriorityQueue

Programação Java
#1

Olá amigos, dêem uma olhada no código abaixo e depois vejam minha discussão :

           Queue q = new PriorityQueue();
	   q.offer(new String("he"));
	   q.offer(new String("hi") );
	   q.offer(new String("by"));
	   q.offer(new String("ba"));
	   q.offer(new String("bb"));
	   q.offer(new String("bc"));

           //q.poll();
	   System.out.println(q + " " + q.size());

saída = [ba, bb, bc, hi, by, he] 6

Eu pensei que PriorityQueue por padrão colocaria os itens em ordem natural (ba, bb, bc, by, he, hi) ou se houvesse um Comparator o conjunto seria organizado de acordo com o Comparator

Não consegui também assimilar o conceito de priority-in priority-out que faz com que se eu tirar o comentario de “q.poll();” faz com que o elemento mais a esquerda seja removido resultando em [bb, bc, by, he, hi] 5. Se inserir outro “q.poll();” na linha debaixo outro item mais a esquerda é retirado resultando em [bc, by, he, hi] 4.

1 - Porque os itens não estão sendo colocados em ordem natural como (ba, bb, bc, by, he, hi)?

2 - Após ele classificar o conjunto os primeiros que entraram são os primeiros que saem quando invocamos poll() (Exemplo invocando poll com um conjunto classificado assim (ba, bb, bc, by, he, hi) serão retirados os elementos da esquerda para a direita certo?) ?

3 - Se o conceito é o primeiro que entra é o primeiro que sai porque o conjunto não foi feito na ordem que os inseri (EX: he, hi, by, ba, bb, bc )?
Pois pelo que vi no livro da kathy o conjunto terá a ordem natural ou a ordem sera de acordo com um Comparator.

Desde já agradeço a ajuda e atenção!

#2

Alguem pode ajudar com este código? :cry:

#3

Um PriorityQueue não conserva seus elementos em “ordem natural”.

Ao usarmos um Iterator para percorrer seus elementos, eles serão retornados em ordem diferente da esperada quando você usa poll ou peek. Ele mostra em uma ordem interna que depende bastante da implementação.

Ele se comporta como se fosse uma fila ordenada, mas em vez de sair primeiro quem entrou primeiro, sai primeiro quem tem valor menor.

Quando você usa o método toString de PriorityQueue, esse método usa o Iterator (ou seja, lista em ordem diferente da esperada), não “peek” ou “poll” senão ele destruiria o conteúdo da fila.

Se você tentar ler o código-fonte de java.util.PriorityQueue (em src.zip, no diretório de instalação do JDK, existe o arquivo compactado /java/util/PriorityQueue.java ) você realmente vai entender o que falei.

#4

Interessante a dúvida, me ajudou a conhecer um pouco mais sobre o assunto.

Resumindo:
O primeiro elemento a sair do PriorityQueue sempre será o que tiver mais prioridade (1 tem mais prioridade que 2…). Caso você não especifique as prioridades, será usado a ordem natural do elemento adicionado (Vale lembrar que PriorityQueue é um conjunto classificado, como TreeSet por exemplo, ou seja não é possível inserir 2 elementos de tipos diferentes).

Insira no seu código:

for(int x=0; x<6; x++) System.out.print(q.poll() + " ");

Verá a saída na ordem natural:
ba bb bc by he hi

Ao executar o método toString() de PriorityQueue (atravez da referência q) é chamado o toString() de AbstractCollection (que é a primeira classe "pai" a sobrescrever o método), que por sua vez utiliza um Iterator para adicionar a uma String. Como não é possível prever a ordem de um Iterator, o código não tem como saída a ordem natural.

Espero ter ajudado.

#5