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;

    }

});

我加上 100,100,101 和 99。

添加 101 时，它会在 100（100 的列表）下方正确添加 101。但是当我加上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.

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

升序堆（min heap）会保证堆顶元素最小。弹出顶部元素后，下一个顶部元素将是剩余元素中最小的。等等。

如果您想要一个已排序元素的列表，您必须通过从堆中弹出来构建它。或者，你可以只使用一个列表，并使用 Collections.sort.

对其进行排序

顺便说一句，正如其他人在评论中指出的那样， compare 方法的实现违反了 Comparator 接口的约定：当恰好 a 和 b 之一为空时， compare(a, b) 和 compare(b, a) returns -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());
}

PriorityQueue 是 Java 不使用自定义比较器降序排列

PriorityQueue is Java does not order descending with custom comparator

java

priority-queue

comparator