具有覆盖比较器的优先队列

Question

我在 Java 中使用 PriorityQueue。

我有一个具有这种结构的对象：

public class CostObject {

  String value;
  double cost;

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

优先级是从最便宜到最贵的成本：

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

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

});

我使用 add 在队列中包含对象。

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

它适用于队列中的每个元素，但我添加的最后一个元素始终位于底部位置。

我究竟做错了什么？

Answer 1

您的比较器永远不会返回 0。这至少违反了Comparator.compare的一般合同中的规则之一，即：

sgn(compare(x, y)) == -sgn(compare(y, x))

如果x和y具有相同的成本，则compare(x, y)和compare(y, x)都将为 -1。

您应该使用Double.compare, 或Comparator.comparingDouble正确实施Comparator：

new PriorityQueue<>(1, new Comparator<>() {
    public int compare(CostObject co1, CostObject co2) {
        return Double.compare(co1.cost, co2.cost);
    }
});

或者：

new PriorityQueue<>(1, Comparator.comparingDouble(CostObject::getCost));

正如 Slimu 在评论中提到的，您可能会使用它的iterator（例如使用 for 循环）从队列中取出元素。这不能保证以正确的顺序为您提供元素，这可能是为什么“但我添加的最后一个，它总是在底部位置”。poll如果您希望元素以正确的顺序排列，您应该从队列中取出。