[SCJP] Dúvida com PriorityQueue

[gervas-IO]

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

[rdgms]

Não sabia também…

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

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

[entanglement]

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

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

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.

[gervas-IO]

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

[gervas-IO]

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.

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

Abs.
Paulo Gervásio.

[entanglement]

[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

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  ...
     */
    private transient Object[] queue;

Garanto que isso não cai no exame.

[gervas-IO]

BLz garoto!
Obrigado, bom fim de semana!