Priority Queue with overrided comparator

Question

I'm using PriorityQueue in Java.

I have an object with this structure:

public class CostObject {

  String value;
  double cost;

  public CostObject(String val, double cst) {
    value = val;
    cost = cst;
  }
}

The priority is the cost from cheapest to most expensive:

PriorityQueue<CostObject> queue = new PriorityQueue<>(1, new Comparator<CostObject> () {

    @Override
    public int compare(CostObject co1, CostObject co2) {
            return (co1.cost > co2.cost) ? 1 : -1;
    }

});

I use add to include objects in the queue.

CostObject co = new CostObject("test", cost);
queue.add(co);

It works for every element in the queue but the last one I add, that is always in the bottom position.

What am I doing wrong?

Answer 1

The priority queue will only guarantee that the head is the cheapest (or smallest/biggest depending on the comparator), but not guarantee on the overall order. if you do queue.poll() to retrieve and remove the head, you will get the elements in order, since every time you poll the current head, the priority queue will make sure the new head is the cheapest element