Trevor Arjeski - 4 months ago 36

Java Question

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`

`@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`

.