带有自定义匿名比较器的 Java 优先级队列

Question

如果这是一个尝试过的问题，请原谅我，但我有点难以弄清楚。

我目前有一个节点类，每个“节点”都是迷宫中的一个正方形。我正在尝试实现 A* 算法，因此每个节点内部都会有一个 f-cost (int) 数据成员。我想知道是否有一种方法可以创建这些节点的优先级队列，并将 f-cost 变量设置为比较器？

我在网上查看了示例，但我所能找到的只是字符串优先级队列。我可以为 Node 类实现 Comparator 吗？这允许我访问存储在其中的数据成员吗？

非常感谢！

Answer 1

绝对地。

您可以使用基于传递给构造函数的匿名 Comparator 的 PriorityQueue：

int initCapacity = 10;
PriorityQueue<Node> pq = new PriorityQueue<Node>(initCapacity, new Comparator<Node>() {
    public int compare(Node n1, Node n2) {
        // compare n1 and n2
    }
});
// use pq as you would use any PriorityQueue

如果您的 Node 类已经实现了 Comparable您甚至不需要定义新的Comparator，因为默认情况下将使用该顺序。除非使用任何其他方法，否则将使用对象之间的自然顺序。

Answer 2

这个问题不久前得到了回答，我想提供一些可用的新选项。

1) 如果您的 Node 类没有实现 Comparator 接口并且您不想（或不能）添加它，则使用 lambda：

  new PriorityQueue<>((node1, node2) -> Integer.compare(node1.getCost(), node2.getCost()));

2) 简单的逆序方法（需要 Node 实现 Comparator接口）：

  new PriorityQueue<>(Comparator.reverseOrder());

3）使用实用函数：

  new PriorityQueue<>(NodeUtil::customCompare);

  public static int customCompare(Node n1, Node n2) {
       return Integer.compare(n1.getCost(), n2.getCost());
  }

Answer 3

public class Node implements Comparable<Node>{

    public int compareTo(Node o) {
         // your comparative function
         return 0;
    }

如果

compareTo 返回负整数，则表示“小于”，0 表示“等于”，1 表示“大于”，

只需一个函数即可使用 PriorityQueue。

编辑：比较是另一种方式，我搞砸了。 -1＜ | 0 = | 1>由于某种原因，我已经从右到左阅读了这些内容。

Answer 4

来自 Java 文档：

基于a的无界优先级队列
优先级堆。这个队列订单
元素按顺序排列
施工时指定，其中
是根据他们指定的
自然顺序（参见可比），或
根据比较器

，PriorityQueues 支持通用数据类型。因此，如果您在 Node 类中实现 Comparable，那么您就可以创建一个 PriorityQueue 并正常使用它。

或者，还有一个构造函数 PriorityQueue(int initialCapacity, Comparator comparator)，它将 Comparator 作为 PriorityQueue 构造函数的一部分。如果您更喜欢此方法，则您的节点类不需要包含继承 Comparable 时所需的额外代码。

Answer 5

java.util中有一个PriorityQueue类。您可以使用它，它将使用自然排序（Node 实现 Comparable）或构造函数中提供的比较器（如果您不希望在 Node 类中使用该代码）。任何类都可以访问另一个类中的任何数据，只要您通过将字段设为非私有（可能是糟糕的 OOP 风格）或提供访问器方法 public int getG()、public int getH()、public int getF() 来允许它。