Trevor Arjeski Trevor Arjeski - 2 months ago 17
Java Question

PriorityQueue not sorting on add

I have a Priority Queue in which I add a Node object to, where the Nodes should be sorted by a value that they contain. For some reason, the priority queue will not sort the Nodes on add. If anyone can see something wrong with this or has any guidance, I appreciate it. Here is a brief example:

PriorityQueue<Node> PQ = new PriorityQueue<Node>();
//for each entry create a node and add it to the PriorityQueue
for(Entry<Character,Integer> entry : entries){
PQ.add(new Node(entry.getKey(),entry.getValue(), true));
}


here is the node's
compareTo
method:

@Override
public int compareTo(Node n) {
if(n.frequency.intValue() > this.frequency.intValue()) return -1;
else if(n.frequency.intValue() == this.frequency.intValue()) return 0;
else return 1;
}

Answer

I guess you expect PriorityQueue to return elements in particular order when you iterate it. However, PriorityQueue doesn't provide such a behaviour, because it's implemented as a priority heap rather than sorted list. From javadoc:

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

The only guarantee provided by PriorityQueue is that poll(), peek(), etc return the least element. If you need ordered iteration of elements, use some other collection such as TreeSet.