实现Java的优先级队列

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; 
     } 



    } 

    }

凡PriorityNode被定义为：实现Java的优先级队列

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; 
     } 


    } 


    }

我在这里使用的比较和实现优先级队列有很多困难 - 请点我在正确的方向。

来源

2010-04-24 Kay

这不完全清楚你的问题是什么。什么是“难度”？编译错误？意外的结果？ – 2010-04-25 10:28:14

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

来源

2010-04-24 02:08:52

这是真的，但我试图完成这种类型的实现之前，审查员对我这样做。 – Kay 2010-04-24 02:14:36

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

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

来源

2010-04-24 02:09:28 coobird

好的，我编辑了代码。 – Kay 2010-04-24 02:18:21

-1

我认为你对自己的评价过于苛刻，优先级队列可以基于阵列的堆高效地实现：更简单和更高效（读取：连续内存区域）。

来源

2011-08-05 07:56:29

那个链接是什么？！ – 2014-03-28 05:37:44

实现Java的优先级队列

回答

相关问题