java Java中的优先队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4011560/
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
Priority Queue in Java
提问by Shonna
can you have 2 parameters? for instance, i want to add a string and a corresponding integer to a priority key. Then I am going to sort it by that integer. I know how to add either a string or a integer, but I dont know how to add both. Can someone please point me in the right direction and let me know if i am even going about this the right way?
你能有2个参数吗？例如，我想向优先级键添加一个字符串和一个相应的整数。然后我将按该整数对其进行排序。我知道如何添加字符串或整数，但我不知道如何添加两者。有人可以指出我正确的方向，让我知道我是否以正确的方式解决这个问题？
回答by NamshubWriter
There are two ways to do this. Either way, you want to create a custom object that holds both the String (the value you want) and the integer (the priority).
有两种方法可以做到这一点。无论哪种方式，您都希望创建一个包含字符串（您想要的值）和整数（优先级）的自定义对象。
The first solution is to have this data object implement Comparable:
第一个解决方案是让这个数据对象实现Comparable：
class Data implements Comparable<Data> {
private final String message;
private final int priority;
public Data(String message, int priority) {
this.message = message;
this.priority = priority;
}
@Override
int compareTo(Data other) {
return Integer.valueOf(priority).compareTo(other.priority);
}
// also implement equals() and hashCode()
}
Then when you do
然后当你做
PriorityQueue<Data> queue = new PriorityQueue<Data>();
the queue will order items by the order defined by the compareTomethod.
队列将按照compareTo方法定义的顺序对项目进行排序。
The problem with this solution is that if you want the ordering to be only on the integer, then either equalsmethod and your compareTomethod will not be consistent or your equalsmethod will not be correct.
此解决方案的问题在于，如果您希望仅对整数进行排序，那么任一equals方法和您的compareTo方法都将不一致，或者您的equals方法将不正确。
A better solution would be to use the PriorityQueueconstructor that takes a Comparator. In this case, Datawouldn't have to implement Comparable; you just need a Comparatorthat defines your ordering:
更好的解决方案是使用带有Comparator的PriorityQueue构造函数。在这种情况下，不必实施；你只需要一个定义你的订购的：DataComparableComparator
public final class OrderDataByPriority implements Comparator<Data> {
public static final OrderDataByPriority INSTANCE = new OrderDataByPriority();
private OrderDataByPriority() {}
@Override
public int compare(Data data1, Data data2) {
return Integer.valueOf(data1.priority).compareTo(data2.priority);
}
@Override
public boolean equals(Object other) {
return other == OrderDataByInteger.INSTANCE;
}
private Object readResolve() {
return INSTANCE;
}
}
Note that since this comparator takes no data, I made it a singleton.
请注意，由于此比较器不接受任何数据，因此我将其设为单例。
You can then create the queue line this:
然后，您可以创建队列行：
PriorityQueue<Data> queue = new PriorityQueue<Data>(
initialCapacity, OrderDataByPrority.INSTANCE);
回答by sandves
Here is a generic way of doing it:
这是一种通用的方法：
public class PriorityQueue<T> {
private java.util.PriorityQueue<IntPriorityComparableWrapper<T>> queue;
public PriorityQueue() {
queue = new java.util.PriorityQueue<IntPriorityComparableWrapper<T>>();
}
public void add( int priority, T object ) {
queue.add( new IntPriorityComparableWrapper<T>(object, priority) );
}
public T get() {
return (null != queue.peek())? queue.poll().getObject() : null;
}
/**
* A "wrapper" to impose comparable properties on any object placed in the
* queue.
*/
private static class IntPriorityComparableWrapper<T>
implements Comparable<IntPriorityComparableWrapper<T>> {
private T object;
private int priority;
public IntPriorityComparableWrapper( T object, int priority ) {
this.object = object;
this.priority = priority;
}
public int compareTo( IntPriorityComparableWrapper<T> anotherObject ) {
return this.priority - anotherObject.priority;
}
public int getPriority() {
return priority;
}
public T getObject() {
return object;
}
}
}
回答by Neeme Praks
How about creating a new classthat contains those two fields (intand String) and then implementing Comparable(comparing on the int field). Don't forget to override also hashCode()and equals()(see the Comparableclass javadoc for reasoning behind overriding these methods).
如何创建一个包含这两个字段（和）的新类，然后实现Comparable（比较 int 字段）。不要忘记也覆盖和（有关覆盖这些方法的推理，请参阅Comparable类 javadoc）。intStringhashCode()equals()
Is that what you are after?
这就是你所追求的吗？
回答by Michael Aaron Safyan
If you want to use multiple elements as a key, you can create a class that encapsulates both, and then use that type as the key. Likewise for the values. You should make this custom key class Comparable, override equals(), and override hashCode()for the custom key class that you create.
如果要使用多个元素作为键，可以创建一个将两者都封装起来的类，然后使用该类型作为键。价值观也是如此。您应该为您创建的自定义密钥类创建此自定义密钥类Comparable、覆盖equals()和覆盖hashCode()。
