Java 优先队列 （PriorityQueue）

基本概念

Priority queue是抽象集合类的一个子类，实现了Queue接口。一方面priority queue提供了标准的队列方法：
将元素放入队列：add，offer
将队首元素从队列删除：remove，poll
查看队列内的对首元素：element，peek

之不过，和标准队列不同的是，当删除队首元素的时候，删除的是priority queue中最小的元素。但是，priority queue并不是对所有的元素排序，其内部是用heap（堆）实现的。堆是一个自组织的二叉树，在这个二叉树里，add和remove操作使得最小的元素“吸引”到二叉树的根部，而不用在排列整个队列上耗费时间。

pq.png

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(3);
        pq.add(2);
        pq.add(1);

        // first debug point
        System.out.println(pq.peek());
        pq.poll();
        // second debug point
        System.out.println(pq.peek());

在第一个debug点：
队列内元素的排列顺序为：1，3，2，也就是说新加入的元素因为最小，所以被放在了队首。

debug1.png

在第二个debug点：
队列内元素的排列顺序为：2，3，删除队首元素后，最小的元素就被“吸引”到了队首。

debug2.png

高级用法

就像TreeSet一样，一个priority queue要么存储的是实现了Comparable接口的元素，要么在构造函数中传入一个Comparator对象。

• Comparable

class PQItem implements Comparable<PQItem>{

    @Override
    public String toString() {
        return Integer.toString(this.getVal());
    }

    @Override
    public int compareTo(PQItem o) {
        return this.getVal() - o.getVal();
    }

    private int val = 0;
    public PQItem(int val){
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }
}

    private static void test2(){
        PriorityQueue<PQItem> pq = new PriorityQueue<>();
        pq.add(new PQItem(3));
        pq.add(new PQItem(2));
        pq.add(new PQItem(1));

        System.out.println(pq.peek());
        pq.poll();
        System.out.println(pq.peek());
    }

• Comparator

    private static void test3(){
        PriorityQueue<PQItemNonSortable> pq = new PriorityQueue<>(new Comparator<PQItemNonSortable>() {
            @Override
            public int compare(PQItemNonSortable o1, PQItemNonSortable o2) {
                return o1.getVal() - o2.getVal();
            }
        });
        pq.add(new PQItemNonSortable(3));
        pq.add(new PQItemNonSortable(2));
        pq.add(new PQItemNonSortable(1));

        System.out.println(pq.peek());
        pq.poll();
        System.out.println(pq.peek());
    }

典型用法

Priority queue的典型用法就是job的schedule。每个job都有一个priority，可以以任何顺序将job添加到priority queue中。当能启动一个新的job的时候，队列中priority最高的job将被删除。