实现 Java 优先级队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2702913/
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
Implementing Java Priority Queue
提问by Kay
public class PriorityQueue<T> {
private PriorityNode<T> head, tail;
private int numItems;
public PriorityQueue(){
numItems = 0;
head=null;
tail=null;
}
public void add(int priority, T value){
PriorityNode<T> newNode = new PriorityNode<T>(priority,value);
if(numItems == 0){
head = newNode;
tail = newNode;
}
else{
head.setNext(newNode);
head = newNode;
}
}
}
Where PriorityNode is defined as:
其中 PriorityNode 定义为：
public class PriorityNode<T> implements Comparable<T> {
private T value;
private PriorityNode<T> next;
private int priority;
public PriorityNode(int priority,T newValue){
value = newValue;
next = null;
priority = 0;
}
public PriorityNode(T newValue){
value = newValue;
next = null;
priority = 0;
}
public void setPriority(int priority){
this.priority = priority;
}
public int getPriority(){
return this.priority;
}
public T getValue(){
return value;
}
public PriorityNode<T> getNext(){
return next;
}
public void setNext(PriorityNode<T> nextNode){
this.next = nextNode;
}
public void setValue(T newValue){
value = newValue;
}
@Override
public int compareTo(int pri) {
// TODO Auto-generated method stub
if(this.priority<pri){
return -1;
}
else if(this.priority == pri){
return 0;
}
else{
return 1;
}
}
}
I'm having a lot of difficulty using the Comparator here and implementing a priority queue - please point me in the right direction.
我在这里使用比较器并实现优先级队列时遇到了很多困难 - 请指出正确的方向。
回答by Marcelo Cantos
回答by coobird
Regarding the implementing of the comparator, implementing the Comparator<T>or Comparable<T>interface requires the public int compareTo(T o)method to be overridden.
关于比较器的实现，实现Comparator<T>orComparable<T>接口需要public int compareTo(T o)重写方法。
In the example code given, the compareTo(T)method is not overridden (the compareTo(int)method is defined, but that is notthe same method signature), therefore, it will probably lead to a compiler error.
在给出的示例代码中，compareTo(T)方法没有被覆盖（compareTo(int)定义了方法，但不是相同的方法签名），因此，它可能会导致编译器错误。
回答by Savino Sguera
I think you are making it a bit too tough on yourself, a priority queue is efficiently implemented with array-based heaps: simpler and more efficient (read: contiguous memory areas).
我认为你对自己太苛刻了，优先队列是用基于数组的堆有效地实现的：更简单、更高效（阅读：连续内存区域）。
