Trevor Arjeski Trevor Arjeski - 1 year ago 94
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

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 Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download