PriorityQueue posortowane, ale dwie największe [duplikaty]

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

WYNIK:

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

Szukam k największych par (ich liczby) w tablicy hashy, a te na wyjściu są w rzeczywistości poprawnymi. Moje pytanie brzmi: dlaczego dwa ostatnie są zamienione?

Answer 1

PriorityQueuezwraca tylko najniższy element z głowy. Nie sortuje wszystkich elementów, więc jeśli przechodzisz przez kolejkę z pq.toString(), elementy mogą nie pojawiać się w kolejności. Dzieje się tak, ponieważ wewnętrznie PriorityQueue.toString()korzysta z tej PriorityQueue.iterator()metody i zgodnie z dokumentacją:

Iteracyjnej dostarczane w sposób iterator()jest nie gwarantuje przechodzą elementy kolejkę priorytetową w określonej kolejności. Jeśli potrzebujesz uporządkowanego przemierzania, rozważ użycie Arrays.sort(pq.toArray()).

Jeśli chcesz wydrukować elementy kolejki priorytetowej w kolejności, powinieneś zmienić ten kod:

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

Do następujących:

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

Answer 2

Metoda toString () klasy PriorityQueue nie gwarantuje kolejności elementów, ponieważ używa iteratora.

Answer 3

Możesz sprawdzić zamówienie metodą ankiety, jak tutaj:

Wydrukuj zawartość kolejki priorytetowej [java]