2 
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 は次のように定義されています。

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


     }


    }

ここで Comparator を使用し、プライオリティ キューを実装するのが非常に困難です。正しい方向を教えてください。

4

3 に答える 3

3

ツリー構造を使用してプライオリティ キューを実装しないでください。ヒープを使用します。スペース効率が高く、必要なメモリ割り当てが少なく、ほとんどの操作で O(log(N)) です。

于 2010-04-24T02:08:52.730 に答える
3

コンパレータの実装に関しては、Comparator<T>orComparable<T>インターフェイスを実装するには、public int compareTo(T o)メソッドをオーバーライドする必要があります。

与えられたサンプル コードでは、compareTo(T)メソッドはオーバーライドされていません (compareTo(int)メソッドは定義されていますが、それは同じメソッド シグネチャではありません)。そのため、コンパイラ エラーが発生する可能性があります。

于 2010-04-24T02:09:28.023 に答える
-1

プライオリティ キューは、配列ベースのヒープで効率的に実装されています。よりシンプルで効率的です (読み取り: 連続したメモリ領域)。

于 2011-08-05T07:56:29.197 に答える