带有自定义匿名比较器的 Java 优先级队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2555284/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java Priority Queue with a custom anonymous comparator
提问by Bharat
Forgive me if this is a tried question, but I'm having a little difficulty figuring it out.
如果这是一个尝试过的问题，请原谅我，但我很难弄清楚。
I currently have a class Node, and each 'node' is a square in a maze. I'm trying to implement the A* algorithm, so each of these nodes will have an f-cost (int) data member inside of it. I was wondering if there's a way that I can create a priority queue of these nodes, and set up the f-cost variable as the comparator?
我目前有一个节点类，每个“节点”都是迷宫中的一个正方形。我正在尝试实现 A* 算法，因此这些节点中的每一个都将在其中包含一个 f-cost (int) 数据成员。我想知道是否有一种方法可以创建这些节点的优先级队列，并将 f-cost 变量设置为比较器？
I've looked at examples online, but all I can find are String priority queues. Can I implement Comparator for the Node class? Would this allow me to access the data member stored inside it?
我在网上看过例子，但我能找到的只是字符串优先级队列。我可以为 Node 类实现 Comparator 吗？这是否允许我访问存储在其中的数据成员？
Many Thanks!
非常感谢！
采纳答案by Yuval Adam
Absolutely.
绝对地。
You can use a PriorityQueuebased on an anonymous Comparatorpassed to the constructor:
您可以使用PriorityQueue基于匿名Comparator传递给构造函数：
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
If your Nodeclass already implements Comparableyou don't even need to define a new Comparator, as that order will be used by default. Barring any other method, the natural ordering between objects will be used.
如果您的Node类已经实现，Comparable您甚至不需要定义 new Comparator，因为默认情况下将使用该顺序。除非使用任何其他方法，否则将使用对象之间的自然顺序。
回答by Justin Ardini
From the Javadocs:
来自 Javadocs：
An unbounded priority queue based on a priority heap. This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator
基于优先级堆的无界优先级队列。此队列根据在构造时指定的顺序对元素进行排序，该顺序是根据它们的自然顺序（请参阅 Comparable）或根据 Comparator 指定的
Furthermore, PriorityQueues support generic data types. Therefore, if you implement Comparablein your Node class, then you can create a PriorityQueue<Node>and use it normally.
此外，PriorityQueues 支持通用数据类型。因此，如果您Comparable在您的 Node 类中实现，那么您可以创建一个PriorityQueue<Node>并正常使用它。
Alternately, there is a constructor PriorityQueue(int initialCapacity, Comparator<? super E> comparator)that takes in a Comparator as part of the PriorityQueueconstructor. If you prefer this method, your node class does not need to contain the extra code needed when inheriting Comparable.
或者，有一个构造函数PriorityQueue(int initialCapacity, Comparator<? super E> comparator)将 Comparator 作为PriorityQueue构造函数的一部分。如果您更喜欢这种方法，则您的节点类不需要包含继承Comparable.
回答by M. Jessup
There is a PriorityQueue class in java.util. You can use that and it will either use natural ordering (Node implements Comparable) or a comparator supplied in the constructor (if you don't want that code inside your Node class). Any class can access any data inside another as long as you allow it either by making a field non-private (potentially bad OOP style) or supplying an accessor method public int getG(), public int getH(), public int getF().
java.util 中有一个 PriorityQueue 类。你可以使用它，它要么使用自然排序（Node 实现 Comparable），要么使用构造函数中提供的比较器（如果你不想在你的 Node 类中使用该代码）。任何类都可以访问另一个类中的任何数据，只要您允许它通过使字段非私有（可能是糟糕的 OOP 样式）或提供访问器方法 public int getG()、public int getH()、public int getF() .
回答by badcodenotreat
public class Node implements Comparable<Node>{
public int compareTo(Node o) {
// your comparative function
return 0;
}
}
}
if compareTo returns a negative int, it means "less than", 0 means "equals", 1 means "greater than"
如果 compareTo 返回负整数，则表示“小于”，0 表示“等于”，1 表示“大于”
that one function is all you need to be able to use PriorityQueue.
使用 PriorityQueue 只需要一个函数即可。
EDIT: comparison is other way, i messed that up. -1 < | 0 = | 1 > i alreays read those right to left for some reason.
编辑：比较是另一种方式，我搞砸了。-1 < | 0 = | 1 > 由于某种原因，我已经从右到左阅读了这些内容。
回答by Ilya Ovesnov
This question was answered a while ago and I want to give some new options that are available.
不久前回答了这个问题，我想提供一些可用的新选项。
1) Using lambda in case if your Nodeclass doesn't implement Comparator interface and you don't want (or can't) add it:
1) 如果您的Node类没有实现 Comparator 接口并且您不想（或不能）添加它，请使用 lambda ：
new PriorityQueue<>((node1, node2) -> Integer.compare(node1.getCost(), node2.getCost()));
2) Simple reverse order approach (require Node to implement Comparator interface):
2）简单的逆序方式（需要Node实现Comparator接口）：
new PriorityQueue<>(Comparator.reverseOrder());
3) Using utility function:
3) 使用效用函数：
new PriorityQueue<>(NodeUtil::customCompare);
public static int customCompare(Node n1, Node n2) {
return Integer.compare(n1.getCost(), n2.getCost());
}
