学步园

PriorityQueue是基于优先级堆的极大优先级队列。

在PriorityQueue提供的构造方法中，可以使用自定义的排序方法：

PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){

            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }

        });

也可以使用元素自带的Comparable排序。

因此，PriorityQueue要求在默认排序的时候，需要元素对象拥有Comparable功能。

若对象元素没有该功能，则无法进行比较和排序，也就会报异常：

Exception in thread "main" java.lang.ClassCastException: Test.webs cannot be cast to java.lang.Comparable
	at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
	at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
	at java.util.PriorityQueue.offer(PriorityQueue.java:329)
	at java.util.PriorityQueue.add(PriorityQueue.java:306)
	at Test.Permutation_Sequence.main(Permutation_Sequence.java:49)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:606)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:134)

但是，若对象在没有Comparable功能的时候，PriorityQueue实现了自己的Comparator，那么理所当然可以正确运行：

PriorityQueue<webs> pq = new PriorityQueue<webs>(3,new Comparator<webs>(){

            @Override
            public int compare(webs o1, webs o2) {
                return o1.n - o2.n;
            }
        });

PriorityQueue提供的方法：

peel():返回队头的元素，但不删除。

poll():返回并删除队首元素。

add():将元素加入队列

offer():同上。

看一下源代码，发现add和offer并无区别：

  public boolean add(E e) {
        return offer(e);
    }

注意：当PriorityQueue每次弹出一个元素的时候，是会根据排序原则排到一个应得的元素（比如最小，最大）。但是剩余元素在PriorityQueue的内部并不是有序排列的。

因此，当使用Iterator时，打印出来的顺序并不是有序的。

public static void main(String[] args){
        PriorityQueue<webs> pq = new PriorityQueue<webs>(3,new Comparator<webs>(){
            @Override
            public int compare(webs o1, webs o2) {
                return o1.n - o2.n;
            }
        });
        webs a = new webs(1);
        webs b = new webs(2);
        webs c = new webs(4);
        webs e = new webs(0);
        webs d = new webs(5);
        pq.add(a);
        pq.add(d);
        pq.add(c);
        pq.add(e);
        pq.add(b);
        while(!pq.isEmpty()){
            Iterator<webs> ite = pq.iterator();
            while(ite.hasNext()){
                webs aa = ite.next();
                System.out.println(aa.n);
            }
            webs tmp = pq.poll();
            System.out.println(tmp.n+"-----------------");
        }
    }

结果如图：

0
1
4
5
2
0-----------------
1
2
4
5
1-----------------
2
5
4
2-----------------
4
5
4-----------------
5
5-----------------