PriorityQueue is Java does not order descending with custom comparator

Question

I'm implementing a sample order book (in Exchange domain) and I'm implementing the buy and the sell sides using PriorityQueue in Java.

Buy side should be descending and sell side should be ascending.

PriorityQueue<ArrayList<Order>> bookSide;

Each side consists of price points, and each point has a list of Orders.

My buy side works fine.

This is my sell side. I want this is to be ordered descending.

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;

    }

});

I add 100,100,101 and 99.

When 101 is added, it correctly adds 101 below 100 (list of 100). But when I add 99, it destroys the order and becomes 99,101,100.

I have no clue what is wrong.

Please help me out.

EDIT

This is how I add the elements to the lists. The price is a 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

It seems there's a misunderstanding about how PriorityQueue works. Let's try to clear that up.

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

First, an important reminder from the Javadoc of PriorityQueue:

An unbounded priority queue based on a priority heap.

The key term here is heap. In a heap, elements are not ordered in a sequence. A heap is a tree-like structure, where every node is consistently ordered compared to every other node below it. In other words, there are no guarantees whatsoever with respect to ordering of nodes at the same level.

A heap in ascending order (min heap) will guarantee that the top element is the smallest. After you pop the top element, the next top element will be the smallest of the remaining elements. And so on.

If you want a list of sorted elements, you have to build it by popping from the heap one by one. Alternatively, you can use just a list, and sort it using Collections.sort.

---

As an aside, and as others pointed out in comments, the implementation of the compare method violates the contract of the Comparator interface: when precisely one of a and b is empty, both compare(a, b) and compare(b, a) returns -1, which implies that a < b and b < a, which breaks logic.

The fix is easy, I also simplified a bit the rest of the implementation:

@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());
}