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?

Please add the code of struc, and the code you use to put/retrieve the values in the queue. Are you iterating the values using an Iterator, or are you using poll() to get/remove the head every time ? — Florent Bayle
– Florent Bayle, Commented Mar 6, 2015 at 15:03
"Ties are broken arbitrarily" means the PQ can do whatever it wants when it sees a tie, including shuffling your input randomly. — Louis Wasserman
– Louis Wasserman, Commented Mar 6, 2015 at 16:55
I used a poll() method to get/remove the head every time. Struc class is just a point class. — Chenwei
– Chenwei, Commented Mar 7, 2015 at 4:23

Ravi K Thapliyal · Accepted Answer · 2015-03-06 15:05:23Z

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.

edited Mar 6, 2015 at 15:05

answered Mar 6, 2015 at 14:58

Ravi K Thapliyal

51.9k9 gold badges80 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Chenwei Over a year ago

I agree with you it's incorrect for program to depend on undefined behaviour for its correctness. I talked with my friend yesterday, He thought this might have something to do with its heap structure.

Louis Wasserman · Accepted Answer · 2015-03-06 16:56:20Z

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.

answered Mar 6, 2015 at 16:56

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

2 Comments

Chenwei Over a year ago

I am trying to implement a FIFO method. If they come at the same time, just first come first serve. =.=

Louis Wasserman Over a year ago

Then you have to add another property to the elements indicating the order they came in; there's no other way to do it.

Collectives™ on Stack Overflow

Priority Queue default ordering

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related