java PriorityQueue 具有相同优先级的对象

PriorityQueue has objects with the same priority

提问by USS1994

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.

例如，如果我按顺序添加 CustomObjects A、B、C、D，所有对象都具有相同的“权重”，那么优先级队列也应该按该顺序返回它们 - 即使我轮询一个或多个对象在添加其他人之前。

Here is the CompareTo for my custom object:

这是我的自定义对象的 CompareTo：

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.

虽然我认为这会保持最初的顺序，但事实并非如此。当我输入权重为 1 的 A、B、C 时会发生这种情况；投票 A; 并以权重 1 添加 D,E。不知何故，D 和 E 排在 B 之后，但在 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.

我知道 PriorityQueues 的迭代器没有返回正确的排序，所以我查看排序的能力受到限制 - 但是我可以看到元素离开队列的顺序并且它显然没有遵循路径我想要它。

Suggestions?

建议？

回答by NPE

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

您可以使用自动递增的序列号作为辅助键，并使用它来打破平局。

Javadoc for PriorityBlockingQueueincludes an example of this technique:

Javadoc forPriorityBlockingQueue包含此技术的示例：

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;
   }
 }

对此类的操作不保证具有相同优先级的元素的顺序。如果您需要强制排序，您可以定义自定义类或比较器，它们使用辅助键来打破主要优先级值之间的联系。例如，这是一个将先进先出打破平局应用于可比元素的类。要使用它，您将插入一个新的FIFOEntry(anEntry)而不是一个普通的条目对象。

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;
   }
 }

回答by Cratylus

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 timestampto see which element was inserted first. So CustomObjectshould be something like:

如果您需要根据插入顺序进行排序，则需要使用额外的元素作为时间戳。即在插入和相等的权重上使用timestamp查看哪个元素首先被插入。所以CustomObject应该是这样的：

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 timestampmeans it was inserted earlierso you keep in the insertion order.

较小timestamp意味着它较早插入，因此您可以保持插入顺序。

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

您还可以通过维护在每个add或上更新的计数器来使用“逻辑”时间remove。