Priority Queue default ordering

Question

Comparator<struc> cmp= new Comparator<struc>() {
  public int compare(struc e1, struc e2) {
    return e1.x - e2.x;
  }
};

struc is point structure. when I offer:

（3,1）（3,2）（3,3）（3,4）

q gives me:

（3,1）（3,4），（3，3）（3,2）

and when I offer:

（3,1）（3,3）（3,2）（3,4）

it gives me:

（3,1）（3,4），（3，2）（3,3）.

What's the logic?

Should it just give the order of key_in sequence since y is not compared? When I checked API,it tells me "An unbounded priority queue based on a priority heap...The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily."

Can someone help explain?

Answer 1

The answer is in the doc you quoted: "Ties are broken arbitrarily" means the PQ can do whatever it wants when it sees a tie, including shuffling your input randomly.

All of your inputs have the same x coordinate, so they all tie, and the priority queue can deal with that "arbitrarily," meaning in any way it wants, without any guarantees.

Answer 2

The order is undefined here because all your points tie with each other since their x co-ordinate values are the same. If you're expecting to have the same order, you should enforce that by modifying your compare() implementation to take into account their y co-ordinate values as well.

And, even if the order was for some reason coming the same, it's incorrect for your program to depend on undefined behaviour for its correctness.