PriorityQueue has objects with the same priority

Question

I'm using a priority queue to sort and use a large number of custom objects. The objects have a "weight" that is their natural ordering. However, different objects that are inserted into the priority queue may have the same "weight". In such cases, I want the priority queue to order them in the same order in which they were put into the queue.

For example, if I add in CustomObjects A,B,C,D in that order, all with the same "weight", than the priority queue should return them in that order as well - even if I poll one or more of the objects before adding in the others.

Here is the CompareTo for my custom object:

public int compareTo(CustomObject o) {
    int thisWeight = this.weight;
    int thatWeight = o.weight;
    if(thisWeight < thatWeight){
        return -1;
    }
    else{
        return 1;
    }
}

While I thought that this would maintain that initial order, it doesn't. This occurs when I input A,B,C with weight 1; poll A; and add D,E also with weight 1. Somehow, D and E are sorted after B, but before C.

I am aware that the Iterator for PriorityQueues doesn't return the correct ordering, so I am limited in my ability to look at the ordering - however I can see the order that the elements leave the queue and it clearly doesn't follow the path that I want it to.

Suggestions?

score 19 · Accepted Answer · edited Nov 24 '16 at 23:22

If you need to have an ordering according the insertion order you need to use an extra element for timestamp. I.e. on insertions and equal weight use timestamp to see which element was inserted first. So CustomObject should be something like:

class CustomObject {  
   int weight;  
   long timestamp;  
}

And the comparison should be:

public int compareTo (CustomObject o) {  
    int thisWeight = this.weight;  
    int thatWeight = o.weight;  
    if (thisWeight != thatWeight) {  
        return thisWeight - thatWeight;  
    }  
    else {  
        return this.timestamp - o.timestamp;  
    }  
}

The smaller timestamp means it was inserted earlier so you keep in the insertion order.

You could also use a "logical" time by maintaining a counter that you update on each add or remove.

I just modified my own compareTo by adding an extra if else statement. But as to the actual meat of the answer - Perfect, thanks! — USS1994, Mar 31 '13 at 17:29
This worked for insertion, but when I do a pop, again the order is changing. Is there a way to fix that? — Mounika, Sep 11 '19 at 17:32

score 15 · Answer 2 · answered Mar 31 '13 at 16:58

You could use an automatically-incremented sequence number as a secondary key, and use it to break ties.

Javadoc for PriorityBlockingQueue includes an example of this technique:

Operations on this class make no guarantees about the ordering of elements with equal priority. If you need to enforce an ordering, you can define custom classes or comparators that use a secondary key to break ties in primary priority values. For example, here is a class that applies first-in-first-out tie-breaking to comparable elements. To use it, you would insert a new FIFOEntry(anEntry) instead of a plain entry object.
class FIFOEntry<E extends Comparable<? super E>>
     implements Comparable<FIFOEntry<E>> {
   final static AtomicLong seq = new AtomicLong();
   final long seqNum;
   final E entry;
   public FIFOEntry(E entry) {
     seqNum = seq.getAndIncrement();
     this.entry = entry;
   }
   public E getEntry() { return entry; }
   public int compareTo(FIFOEntry<E> other) {
     int res = entry.compareTo(other.entry);
     if (res == 0 && other.entry != this.entry)
       res = (seqNum < other.seqNum ? -1 : 1);
     return res;
   }
 }

PriorityQueue has objects with the same priority

2 Answers2

Linked