12

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

例如，如果我按该顺序添加 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；并添加权重为 1 的 D，E。不知何故，D 和 E 排序在 B 之后，但在 C 之前。

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

建议？

4

2 回答 2

16

如果您需要根据插入顺序进行排序，则需要为时间戳使用额外的元素。即关于插入和等重使用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。

于 2013-03-31T16:58:28.910 回答
14

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

Javadoc forPriorityBlockingQueue包含此技术的一个示例：

此类上的操作不保证具有相同优先级的元素的顺序。如果您需要强制执行排序，您可以定义自定义类或比较器，它们使用辅助键来打破主要优先级值的关系。例如，这里有一个类将先进先出的平局应用于可比较的元素。要使用它，您将插入一个新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;
   }
 }
于 2013-03-31T16:58:00.977 回答