PriorityQueue具有相同优先级的对象

Question

我正在使用优先级队列来排序和使用大量自定义对象.物体具有"重量",这是它们的自然顺序.但是,插入优先级队列的不同对象可能具有相同的"权重".在这种情况下,我希望优先级队列按照它们放入队列的顺序对它们进行排序.

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

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

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

虽然我认为这将保持初始顺序,但事实并非如此.当我输入重量为1的A,B,C时会发生这种情况; 民意调查A; 并且添加D,E也使用权重1.不知何故,D和E在B之后排序,但在C之前.

我知道PriorityQueues的Iterator没有返回正确的顺序,所以我的查看顺序有限 - 但是我可以看到元素离开队列的顺序,它显然不遵循路径我希望它.

建议？

Answer 1

您可以使用自动递增的序列号作为辅助密钥,并使用它来断开关系.

Javadoc for PriorityBlockingQueue包含了这种技术的一个例子:

此类的操作不保证具有相同优先级的元素的排序.如果需要强制执行排序,则可以定义使用辅助键来断开主要优先级值中的关系的自定义类或比较器.例如,这是一个将先进先出的打破平局应用于可比元素的类.要使用它,您将插入一个新的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;
   }
 }

Answer 2

如果您需要根据插入顺序进行排序,则需要使用额外的元素作为时间戳.即插入和等重量使用,timestamp以查看首先插入的元素.所以CustomObject应该是这样的:

class CustomObject {  
   int weight;  
   long timestamp;  
}

比较应该是:

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

较小的timestamp意思是它之前插入,因此您保持插入顺序.

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