优先级队列

队列是一种先进先出的数据结构，这一点刚好和栈相反。

但是队列的先进先出是根据顺序来决定出队列的元素，而优先级队列可以做到根据优先级出队列

基本介绍

优先级队列有两种:

PriorityQueue ：线程不安全
PriorityBlockingQueue：线程安全

这里主要介绍PriorityQueue，其中PriorityQueue的底层是堆(以后遇到了再总结)，堆的底层是数组。

PriorityQueue的构造器：

构造器	解释说明
public PriorityQueue()	无参构造器
public PriorityQueue(int initialCapacity)	指定容量为initialCapacity的构造器
public PriorityQueue(Comparator<? super E> comparator)	指定集合元素的构造器
public PriorityQueue(int initialCapacity,Comparator<? super E> comparator)	指定初始容量和集合的构造器

使用细节：

PriorityQueue中放置的元素必须要能够比较大小（只有实现了 Comparable 和 Comparator 接口的类才能比较大小），不能插入无法比较大小的对象，否则会抛出 ClassCastException 异常
不能插入 null 对象，否则会抛出 NullPointerException 异常
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
插入和删除元素的时间复杂度均为 O(log2N)
PriorityQueue底层使用了堆数据结构

PriorityQueue中，最小的元素为优先级最高的元素

常用方法

api	介绍
boolean offer(E e)	插入元素e,如果e为空抛出NullPointerException异常，否则返回true
E peek()	获取优先级最高的元素，如果优先级队列为空，返回 null
E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回 null
int size()	获取有效元素的个数
void clean()	清空
boolean isEmpty()	检测优先级队列是否为空，空返回 true

特别的入队列和出队列

操作	抛异常	返回特殊值
入队列	add(e)	offer(e)
出队列	remove()	poll()
获取队首元素	element()	peek()

其中有自动扩容的方法，即grow()

应用实例

合并k个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        //匿名内部类，用lombota表达式简述了
        PriorityQueue<ListNode> queue = new PriorityQueue<>(
            lists.length,(a,b)->(a.val-b.val)
        );
        ListNode res = new ListNode(-1);
        ListNode p = res;
        for(ListNode node : lists){
            if(node != null) queue.add(node);
        }
        while(!queue.isEmpty()){
            //每次找的都是所有链表内的最小值
            ListNode node = queue.poll();
            p.next = node;
            if(node.next!=null) queue.add(node.next);  //把剩下的节点继续加入优先级队列内，继续往下寻找
            p = p.next;
        }
        return res.next;
    }
}