PriorityQueue sorted but the two biggest

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

OUTPUT:

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

I am looking for the k biggest Pairs (their number) in the hashtable and those on the output are in fact the correct ones. My question is, why are the last two swapped?

Answer 1

PriorityQueue only returns the lowest element from its head. It doesn't sort all the elements, so if you traverse the queue with pq.toString(), elements may not appear in order. This happens because, internally, PriorityQueue.toString() uses the PriorityQueue.iterator() method and, according to the docs:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

If you want to print the elements of the priority queue in order, you should change this code:

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

To the following:

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

Answer 2

The toString() method of the PriorityQueue class does not guarantee you the order of the elements as it uses an iterator.

Answer 3

You can check the order using poll method as here:

Print content of priority queue[java]