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

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

你的比较器永远不会 return 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。

Answer 2

优先级队列只会保证头部是最便宜的（或者smallest/biggest取决于比较器），但不保证整体顺序。如果你做 queue.poll() 到 retrieve 和 remove 头部，你会得到有序的元素，因为每次轮询当前head，优先队列会确保新的head是最便宜的元素

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

Priority Queue with overrided comparator

java

priority-queue