順序付けされていないリンクリストで優先度キューを実装する方法

Question

優先度キューをの順序なしリンクリストで実装する考えがあります。

public class UnorderedLinkedListMaxPQ<Key extends Comparable<Key>> { 
    private Node first; 
    private int n;          //number of elements 
    private class Node{ 
     Key key;           //elements 
     Node next; 
    } 

    public boolean isEmpty()    {return first==null;} 
    public int size()      {return n;} 
    public void insert(Key key){ 
     Node oldfirst=first; 
     first=new Node(); 
     first.key=key; 
     first.next=oldfirst; 
     n++; 
    } 

    public Key delMax(){ 
     Node node=first; 
     if(node==null) {return null;} 
     Key max=node.key; 
     while(node.next!=null){ 
      Key data=node.next.key; 
      if(data.compareTo(max)>0){ 
       max=data; 
      } 
      node=node.next; 
     } 
     first=first.next; 
      n--; 
     return max; 
    } 

    //Test Routine 
    public static void main(String[] args) { 
     UnorderedLInkedListMaxPQ<String> pq=new UnorderedLInkedListMaxPQ<String>(); 
     pq.insert("this"); 
     pq.insert("is"); 
     pq.insert("a"); 
     pq.insert("test"); 

     for(int j=0;j<pq.n;j++){ 
      StdOut.print(pq.delMax()); 
      StdOut.println(); 

     } 
    } 
} 

リンクリストのmax要素を検索し、maxest要素を返します。 しかし、私がテストすると、this thisの出力はthis test is aとなります。

私の道具に何か問題がありますか？何か提案がありますか？

Answer 1

パフォーマンス上の理由から、これは優先キューを実装する最適な方法ではありません。私は挿入中に順序付きリストを保持することをお勧めします。このようにすると、最初にmaxを検索し、リンクされたリスト全体をスキャンしないで削除するだけです。

しかし、場合には、あなたは現在のアプローチに固執したい、（delMaxを変更する）次のように：

public Key delMax(){ 

    if(first==null) 
     return null; 
    else if(n==1) 
     return first.key; 
    Node max=first,maxPrev=null,curr = max.next,prev = first; 
    while(curr!=null){ 
     Key currMax = max.key; 
     Key nextKey = curr.key; 
     if(nextKey.compareTo(currMax)>0){ 
      max = curr; 
      maxPrev = prev; 
     } 
     prev = curr; 
     curr = curr.next; 
    } 
    if(maxPrev!=null) 
     maxPrev.next=max.next; 
    else 
     first = max.next; 
    n--; 
    return max.key; 
} 

はまた次のように変更します。

int k = pq.n; 
for(int j=0;j<k;j++){ 
    StdOut.print(pq.delMax()); 
    StdOut.println(); 
} 

これはあなたの所望の出力を返す必要がありますthis test is a