[原]自己实现的优先队列 PriorityQueue

    java库里的PriorityQueue无法满足我，它不能固定容量，不遍历（遍历后就无序了），它的排序因字是从小到大（虽然可以用Comparator来反转大小顺序）。我所要的是可以固定容量（在一大堆数据通信中选择最大或最小的几个数时很有用），可遍历（不是一个个poll()）。
    于是，在有空的时间里写了一下。内容是一个双向链表（带头的，头不作保存数据），用插入排序。个人认为一个个添加的用插入排序效果比较好。从队尾到队头找合适的插入位置，是稳定的排序。
    添加的实体可以用Comparator或Comparable，如果这两个都不是，就失去排序的效果。实现了比较高兴，发表下。

package net.blogjava.chenlb.util;

import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.Iterator;

/**
 * @param <E>
 * 容量capacity大于0,最多只能添加capacity个,多出的被删除掉.<br/>
 * 删除时根据{@link Comparable}或{@link Comparator} 和 desc
 * 如果comparator==null时使用Comparable<br/>
 * non-thread safe
 * @author chenlb 2008-4-23 下午11:31:06
 */
public class TopPriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {

    private static final long serialVersionUID = 1L;

    private int size;
    private LinkedItem head;
    private LinkedItem last;
    private int top;    //top>0后,容量有限制
    private Comparator<? super E> comparator;
    private boolean desc;    //降序
    
    /**
     * 容量无限制,升序.
     */
    public TopPriorityQueue() {
        this(0, null, false);
    }
    
    /**
     * 容量无限制,
     * @param desc true为降序.
     */
    public TopPriorityQueue(boolean desc) {
        this(0, null, desc);
    }

    /**
     * 容量无限制,升序,用comparator排序
     */
    public TopPriorityQueue(Comparator<? super E> comparator) {
        this(0, comparator, false);
    }
    
    /**
     * 容量无限制,用comparator排序
     * @param desc true为降序
     */
    public TopPriorityQueue(Comparator<? super E> comparator, boolean desc) {
        this(0, comparator, desc);
    }
    

    /**
     * 容量限制为capacity.超出容量限制的,会删除优先级最小(队尾).
     */
    public TopPriorityQueue(int capacity) {
        this(capacity, null, false);
    }
    
    public TopPriorityQueue(int capacity, boolean desc) {
        this(capacity, null, desc);
    }
    
    public TopPriorityQueue(int capacity, Comparator<? super E> comparator) {
        this(capacity, comparator, false);
    }
    
    public TopPriorityQueue(int capacity, Comparator<? super E> comparator, boolean desc) {
        head = new LinkedItem();
        last = head;
        top = capacity;
        this.comparator = comparator;
        this.desc = desc;
    }
    @Override
    public Iterator<E> iterator() {
        // TODO 迭代器
        return new It(head);
    }

    @Override
    public int size() {
        return size;
    }

    
    public boolean offer(E o) {
        // TODO 添加到适当的位置
        if(o == null) {
            throw new IllegalArgumentException("不能添加值为null的!");
        }
        LinkedItem temp = new LinkedItem(o);
        /*last.next = temp;
        temp.prev = last;*/
        if(last == head) {    //第一个
            last.next = temp;
            temp.prev = last;
            
            last = temp;
        } else {
            LinkedItem tempPrev = last;
            if(comparator != null) {
                while(tempPrev!=null && tempPrev != head) {
                
                    int r = comparator.compare(tempPrev.data, temp.data);
                    if(desc) {
                        r = 0 - r;
                    }
                    if(r == 1) {    //tempPrev > temp
                        //重置,继续向前找
                        tempPrev = tempPrev.prev;
                    } else {    //找到插入的位置
                        break;
                    }
                }
                
            } else if(o instanceof Comparable) {    //用Comparable
                
                while(tempPrev!=null && tempPrev != head) {
                    Comparable<E> tPrev = (Comparable<E>) tempPrev.data;
                    int r = tPrev.compareTo(temp.data);
                    if(desc) {
                        r = 0 - r;
                    }
                    if(r == 1) {    //tempPrev > temp
                        //重置,继续向前找
                        tempPrev = tempPrev.prev;
                    } else {    //找到插入的位置
                        break;
                    }
                }
            }
            if(tempPrev != null) {    //插入
                if(tempPrev == last) {    //后面添加的
                    last = temp;
                }
                
                temp.next = tempPrev.next;
                if(tempPrev.next != null) {
                    tempPrev.next.prev = temp;
                }
                tempPrev.next = temp;
                temp.prev = tempPrev;
            }
        }
        
        size++;
        if(top > 0 && size > top) {    //去掉优先级最小的
            tail();
        }
        return true;
    }

    /**
     * 从栈底去除
     */
    public E tail() {
        if(last == head) {
            return null;
        }
        LinkedItem laster = last;
        last = last.prev;
        last.next = null;
        laster.prev = null;
        size--;
        return laster.data;
    }
    
    public E peek() {
        // TODO 取得栈顶值
        LinkedItem first = head.next;
        if(first != null) {
            return first.data;
        }
        return null;
    }

    
    public E poll() {
        // TODO 从栈顶去除
        LinkedItem first = head.next;
        if(first != null) {
            head.next = first.next;
            if(first.next != null) {
                first.next.prev = head;
            }
            size--;
            return first.data;
        }
        return null;
    }

    private class It implements Iterator<E> {

        LinkedItem curr;
        
        public It(LinkedItem curr) {
            super();
            this.curr = curr;
        }

        
        public boolean hasNext() {
            if(curr != null && curr.next != null) {
                return true;
            }
            return false;
        }

        
        public E next() {
            curr = curr.next;
            E d = curr.data;
            return d;
        }

        
        public void remove() {
            curr.prev.next = curr.next;
            if(curr.next != null) {
                curr.next.prev = curr.prev;
            }
            size--;
        }
        
    }
    
    /**
     * @param <E>
     * 链结点.
     * @author chenlb 2008-5-4 下午04:48:17
     */
    private class LinkedItem {
        LinkedItem prev;
        E data;
        LinkedItem next;
        public LinkedItem() {
        }
        public LinkedItem(E o) {
            this.data = o;
        }
    }
}

评论

5 楼 moshalanye 2008-07-01  

lucene 2.32 中用来实现查询结果存放缓存的时候    在代码里有一个这样的实现可以去看下得
org.apache.lucene.util.PriorityQueue  这个是抽象类，里面也有它的实现

4 楼 stephen 2008-06-12  

引用

于是，在有空的时间里写了一下。内容是一个双向链表（带头的，头不作保存数据），用插入排序。个人认为一个个添加的用插入排序效果比较好。从队尾到队头找合适的插入位置，是稳定的排序。

这样来看，这个就是一个排序的双向链表而已。当然，由于有了排序，也可以当作优先队列来用。只是要看数据的规模，这种双向链表的插入在数据量比较大的情况下，需要做的比较次数太多了。
算法书上通常会提到用 heap 结构来实现优先队列，主要是考虑在大规模的数据量情况，heap 是一种性能比较好的结构，在优先队列的使用场景中比二叉树更好一点。

3 楼 llade 2008-06-12  

取决于你需要解决的问题，插入排序用TreeSet。
插入和移除手段可以多样，真正要关注的是否需要多线程访问。

2 楼 chenlb 2008-05-25  

现在我用的是插入排序,链表的.

1 楼 chenlb 2008-05-25  

或许已经有第三方的库类似实现，各位朋友推荐下。