Java PriorityQueue appears to be in the wrong order

Question

I'm trying to make make a program that solves the Minimum Spanning Tree problem. To do this, I have a priority queue of Edge objects which should be sorted according to their corresponding weight field (after that it doesn't really matter, but I've been going by node names).

I'm using the java.util.PriorityQueue. I've tried just about everything but no way I can think of to implement the compareTo() function works. It sorts most of the edges correctly, but not all of them. Here's the code for the most basic compareTo() function I could think of:

@Override
public int compareTo(Object other) {
    return toString().compareTo(((Edge) other).toString());
}

The toString() function outputs first the weight, then the two nodes, so if two nodes A and B were connected with weight 4 it would output

4AB

After putting in a sample graph I end up with the following priority queue:

[1AB, 1BA, 1FH, 2CB, 1CG, 1GC, 1HF, 2EB, 2CD, 3EG, 2BC, 2BE, 3AC, 2GH, 2HG, 5AD, 5EC, 3ED, 2EF, 5CE, 4FD, 2FE, 4FG, 5DA, 2DC, 3GE, 4GF, 3DE, 3CA, 4DF]

Clearly this is not in order, but basically every method of comparing I can think of yields this result.

Can you post more of your code, including the node class, where you're placing things in the queue, and how you end up with the resulting list? — doggie_breath, Oct 28 '15 at 18:41
Post the code you use to display the queue. I'll bet dollars to donuts that your problem is there. If you use the retrieval methods to print out the values, you'll get the correct order. — Kayaman, Oct 28 '15 at 18:42
If you're referring to Java's built-in priority queue, have a look at this: http://stackoverflow.com/questions/5695017/priorityqueue-not-sorting-on-add — Bart Kiers, Oct 28 '15 at 18:42
Note, by the way, that your string-based comparison is inherently flawed in that it will not correctly handle weights greater than 9. That doesn't explain the particular mis-ordering you present, but it's a good reason to build a proper `compareTo()` (or a proper `Comparator` implementation) that performs a *bona fide* numeric comparison. — John Bollinger, Oct 28 '15 at 18:47
What would be the output for `Arrays.sort(priorQue.toArray())` ? — MaxZoom, Oct 28 '15 at 19:16
See http://stackoverflow.com/questions/2277430/the-built-in-iterator-for-javas-priorityqueue-does-not-traverse-the-data-struct — Raedwald, Feb 22 '16 at 14:35

score 0 · Accepted Answer · answered Oct 28 '15 at 19:01

There's nothing wrong here. What you are printing appears to be the result of toString(), which is in not guaranteed to be in any particular order.

When you consume the queue by removing or peeking at the head, however, a minimal element—as defined by your comparator—will result. The queue as a whole is not ordered; the order only determines the head of the queue, and only certain operations specified to operate on the head are affected by the order. The toString() and iterator() methods are not among these operations.

Your comparator should compare weights numerically, rather than as strings. Using string comparison for the edge as a tie-breaker for edges with equal weight is okay, but consider whether you'll have two edges with opposite directions, and if they need special care.

@MaxZoom I'm referring to the `toString()` method of `PriorityQueue` (which is inherited from `AbstractCollection`). — erickson, Oct 28 '15 at 19:19

Java PriorityQueue appears to be in the wrong order

1 Answers1