实现Java优先级队列

public class PriorityQueue { private PriorityNode head, tail; private int numItems; public PriorityQueue(){ numItems = 0; head=null; tail=null; } public void add(int priority, T value){ PriorityNode newNode = new PriorityNode(priority,value); if(numItems == 0){ head = newNode; tail = newNode; } else{ head.setNext(newNode); head = newNode; } } } 

其中PriorityNode定义为：

  public class PriorityNode implements Comparable { private T value; private PriorityNode 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 getNext(){ return next; } public void setNext(PriorityNode 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; } } } 

我在这里使用比较器并实现优先级队列时遇到了很多困难 – 请指出我正确的方向。

Answer 1

不要使用树结构来实现优先级队列。 使用堆 。 它更节省空间，需要更少的内存分配，并且对于大多数操作而言是O（log（N））。

Answer 2

关于比较器的实现，实现Comparator或Comparable接口需要重写public int compareTo(T o)方法。

在给出的示例代码中， compareTo(T)方法未被覆盖（ compareTo(int)方法已定义，但这不是相同的方法签名），因此，它可能会导致编译器错误。

Answer 3

我认为你对自己有点过于强硬，优先级队列可以通过基于数组的堆高效实现：更简单，更高效（读取：连续的内存区域）。