如何用无序链表实现优先级队列

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();

        }
    }
}

我搜索链表中的最大元素，然后return最大元素。但是当我测试时，输出是 this this 我想是 this test is a.

我的工具有问题吗？有什么建议吗？

Answer 1

在性能方面，这不是实现优先级队列的最佳方法。我建议在插入时保留一个有序列表。通过这样做，你只需要删除第一个来检索最大值而不是扫描整个链表。

但如果您想坚持使用当前方法，请按如下方式修改 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();
}

这应该 return 您想要的 this test is a

输出

如何用无序链表实现优先级队列

How to implement priority queue with unordered linkedlist

java

algorithm

priority-queue