PriorityQueue是Java不按順序降序與自定義比較器

Question

我正在實施示例訂單簿（在Exchange域中），我正在使用Java中的PriorityQueue實現購買和銷售方面。

買方應該是降序和賣方應該是升序。

PriorityQueue<ArrayList<Order>> bookSide; 

每邊都包含價格點，每個點都有一個訂單列表。

我的購買方工作正常。

這是我的賣方。我想這是要降序。

sellSide = new PriorityQueue<ArrayList<Order>>(new Comparator<ArrayList<Order>>() { 

    @Override 
    public int compare(ArrayList<Order> arg0, ArrayList<Order> arg1) { 
     // below two conditions are highly unlikely to happen 
     // as the the elements are added to the list before the list is 
     // added to the queue. 
     if (arg0.size() == 0) { 
      return -1; 
     } 
     if (arg1.size() == 0) { 
      return -1; 
     } 
     // all the elements in a list have a similar price 
     Order o1 = arg0.get(0); 
     Order o2 = arg1.get(0); 
     int r = (int) (o1.getPrice() - o2.getPrice()); 
     return r; 

    } 

}); 

我添加100100101和99

當101被加入，它正確添加101低於100（100列表）。但是當我添加99時，它會破壞訂單併成爲99,101,100。

我不知道什麼是錯的。

請幫我一把。

編輯

這是我如何將這些元素添加到列表中。 price是long。

ArrayList<Order> pricePoint = sidePoints.get(price); 
if (pricePoint == null) { 
    pricePoint = new ArrayList<>(); 
    pricePoint.add(order); // I want the list to be non-empty when adding to queue 
    bookSide.add(pricePoint); 
} else { 
    pricePoint.add(order); 
} 

Answer 1

看起來對PriorityQueue的工作原理有一個誤解。 讓我們嘗試清除。

但是，當我添加99時，它破壞了順序，併成爲99,101,100。

首先從Javadoc of PriorityQueue一個重要的提醒：

基於優先級堆的無界優先級隊列。

這裏的關鍵術語是堆。 在堆中，元素不按順序排序。 堆是一棵樹狀結構， 其中每個節點始終有序相比其他節點低於它。 換句話說， 對於同一級別的節點排序沒有任何保證。

以升序排列的堆（最小堆）將保證頂層元素最小。 彈出頂部元素 後，下一個頂部元素將成爲剩餘元素中最小的元素。 依此類推。

如果你想要一個排序元素的列表， 你必須通過從堆中一個接一個地彈出來構建它。 或者， 您只能使用列表 並使用Collections.sort對其進行排序。

---

順便說一句， 和其他人在評論中指出， 比較方法的實現違反Comparator接口的合同： 當a正是一個和b是空的， 都compare(a, b)和compare(b, a)返回-1, ，這意味着a < b和b < a, 其中斷邏輯。

解決方法是容易的，我還簡化了一下實現的其餘部分：

@Override 
public int compare(ArrayList<Order> arg0, ArrayList<Order> arg1) { 
    if (arg0.isEmpty()) { 
    return -1; 
    } 
    if (arg1.isEmpty()) { 
    return 1; 
    } 

    return Integer.compare(arg0.get(0).getPrice(), arg1.get(0).getPrice()); 
}