PriorityQueue classificado, mas os dois maiores [duplicado]

Question

public class Pair implements Comparable<Pair>{
    public String name;
    public int number;

    public int compareTo(Pair other) {
        if (other == null) {
            return 1;
        }
        return Integer.compare(number, other.number);
    }
}

ht = new Hashtable<String, Pair>(perLen);
PriorityQueue<Pair> pq = new PriorityQueue<Pair>(k);
set = ht.keySet();
for (String i: set) {
        tmp0 = ht.get(i);
        if (tmp0.compareTo(pq.peek()) > 0) {
            if (pq.size() == k) {
                pq.remove();
            }
            pq.add(tmp0);
        }
}
System.out.println(pq.toString());

RESULTADO:

[OSCAR 822, ALBERTO 827, DAVID 1523, JAVIER 943]

Estou procurando os k maiores pares (seu número) na tabela de hash e aqueles na saída são de fato os corretos. Minha pergunta é: por que os dois últimos foram trocados?

Answer 1

PriorityQueueretorna apenas o elemento mais baixo de sua cabeça. Ele não classifica todos os elementos, portanto, se você atravessar a fila com pq.toString(), os elementos podem não aparecer em ordem. Isso ocorre porque, internamente, PriorityQueue.toString()utiliza o PriorityQueue.iterator()método e, conforme a documentação:

O Agente Iterativo fornecido no método nãoiterator() tem garantia de atravessar os elementos da fila de prioridade em qualquer ordem específica. Se você precisar de uma travessia ordenada, considere o uso .Arrays.sort(pq.toArray())

Se você deseja imprimir os elementos da fila de prioridade em ordem, você deve alterar este código:

System.out.println(pq.toString());

Para o seguinte:

while (!pq.isEmpty()) 
    System.out.println(pq.remove());

Answer 2

O método toString () da classe PriorityQueue não garante a ordem dos elementos, pois usa um iterador.

Answer 3

Você pode verificar o pedido usando o método de votação aqui:

Imprimir o conteúdo da fila prioritária [java]