實現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的優先級隊列

回答

相關問題