PriorityQueue具有相同優先級的對象

我正在使用優先級隊列來排序和使用大量的自定義對象。對象有一個「重量」，這是他們的自然順序。但是，插入優先級隊列的不同對象可能具有相同的「權重」。在這種情況下，我希望優先級隊列按照它們放入隊列的順序排序。例如，如果我按照該順序添加CustomObjects A，B，C，D，所有與優先級隊列具有相同的「權重」的應按順序返回它們 - 即使我輪詢了一個或在添加其他對象之前更多的對象。PriorityQueue具有相同優先級的對象

這裏是的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不返回正確的順序，所以我受限於我查看排序的能力 - 但是我可以看到元素離開隊列的順序，而且顯然不遵循我希望的路徑。

對此提出建議？

來源

2013-03-31 USS1994

如果你需要有根據你需要使用一個額外的元素的時間戳的插入順序排序。也就是說在插入和等重使用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-31 16:58:28 Cratylus

@Stephan：更新回答 – Cratylus

我剛剛通過添加一個額外的if語句來修改我自己的compareTo。但對於答案的實際肉 - 完美，謝謝！ – USS1994

您可以使用自動遞增的序列號作爲輔助鍵，並使用它來打破關係。

Javadoc中PriorityBlockingQueue包括這種技術的一個例子：在這個類

操作作出關於具有相同優先級元素的順序沒有保證。如果您需要強制執行排序，則可以定義使用輔助鍵的自定義類或比較器來打破主要優先級值中的關係。例如，這裏有一個類將先進先出的tie-breaking應用於可比較的元素。要使用它，你會插入一個新的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-31 16:58:00 NPE

PriorityQueue具有相同優先級的對象

回答

相關問題