[SCJP] Dúvida com PriorityQueue

Olá!

Estou com uma dúvida com relação ao PriorityQueue

Vejam o exemplo:

[code] Queue q = new PriorityQueue();
q.add(“3”);
q.add(“1”);
q.add(“2”);

	System.out.println(q);[/code]

A saída desse programa é [1, 3, 2], mas não consigo entender porque…
não deveria ser [3,1,2] ou no máximo [1,2,3]?

Grato.
Paulo Gervásio

Não sabia também…

link:
http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Quando você imprime uma PriorityQueue, ele não usa “poll” para pegar os elementos. Se você usasse “poll”, iria pegar os elementos na ordem “1”, “2” e “3” como você estaria esperando.

Em vez disso, toString() usa apenas o Iterator, e esse Iterator, em vez de pegar os elementos na ordem em que eles seriam recuperados pelo método “poll”, pega os elementos como eles estão organizados na estrutura de dados usada para implementar a PriorityQueue. A ordem não foi definida, tanto é que o Javadoc diz que os resultados não serão retornados na ordem natural.

http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html#iterator()

De qualquer maneira, na prova isso não é pedido - na prova eles só perguntam como é que funcionam “offer”, “peek” e “poll”, não qual é a ordem do Iterator.

hum… legal!
Mas qual é essa ordem? Como faço pra saber em que ordem os elementos ficarão?

Olá, entanglement
Eu encontrei essa q questão justamente em um mock…
bem bacana por sinal!
http://scjptest.com

Abs.
Paulo Gervásio.

[quote=gervas-IO]hum… legal!
Mas qual é essa ordem? Como faço pra saber em que ordem os elementos ficarão?[/quote]

A ordem em que os objetos ficarão se forem obtidos com “poll” é a ordem crescente. No máximo é isso que irão pedir no exame.

A ordem do iterador não está definida, e pronto. É o que está escrito no Javadoc.

Em caso de dúvidas, estude o fonte de java.util.PriorityQueue, e veja se é possível determinar a ordem exata de forma trivial.

O fonte indica que é usado um “heap binário balanceado”. Veja: http://en.wikipedia.org/wiki/Binary_heap

Garanto que isso não cai no exame.

BLz garoto!
Obrigado, bom fim de semana!