java - PriorityQueue 是 Java 不按自定义比较器降序排列

Question

这个问题已经有答案了:

Iterating through PriorityQueue doesn't yield ordered results (3 个回答)

已关闭 6 年前。

我正在实现一个示例订单簿(在 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;

    }

});

我添加 100,100,101 和 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 存在误解作品。让我们尝试澄清这一点。

But when I add 99, it destroys the order and becomes 99,101,100.

首先，来自 Javadoc of PriorityQueue 的重要提醒:

An unbounded priority queue based on a priority heap.

这里的关键术语是堆。在堆中，元素不按顺序排列。堆是一种树状结构，其中每个节点与其下面的每个其他节点相比都是一致排序的。换句话说，对于同一级别的节点排序没有任何保证。

按升序排列的堆(最小堆)将保证顶部元素是最小的。弹出顶部元素后，下一个顶部元素将是剩余元素中最小的。等等。

如果你想要一个已排序元素的列表，你必须通过从堆中逐一弹出来构建它。或者，你可以只使用一个列表，并使用 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());
}