Arquivo Discussoes de Programacao e Tecnologia Olá!
Estou com uma dúvida com relação ao PriorityQueue
Vejam o exemplo:
Queue<String> q = new PriorityQueue<String>();
q.add("3");
q.add("1");
q.add("2");
System.out.println(q);
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.
hum… legal!
Mas qual é essa ordem? Como faço pra saber em que ordem os elementos ficarão?
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!