PriorityQueue（优先队列）结合leetcode23. 合并K个升序链表 (趁热打铁，应用在算法，简化直观）

PriorityQueue类是一种队列数据结构实现，其中根据优先级处理对象。它与遵循FIFO（先进先出）算法的标准队列不同。

在优先级队列中，添加的对象根据其优先级。默认情况下，优先级由对象的自然顺序决定。队列构建时提供的比较器可以覆盖默认优先级。

1. PriorityQueue功能

让我们记下PriorityQueue上的几个要点。

PriorityQueue是一个无限制的队列，并且动态增长。默认初始容量'11'可以使用相应构造函数中的initialCapacity参数覆盖。
它不允许NULL对象。
添加到PriorityQueue的对象必须具有可比性。
默认情况下，优先级队列的对象按自然顺序排序。
比较器可用于队列中对象的自定义排序。
优先级队列的头部是基于自然排序或基于比较器的排序的最小元素。当我们轮询队列时，它从队列中返回头对象。
如果存在多个具有相同优先级的对象，则它可以随机轮询其中任何一个。
PriorityQueue 不是线程安全的。PriorityBlockingQueue在并发环境中使用。
它为add和poll方法提供了O（log（n））时间。

1. PriorityQueue功能

让我们看看对象的排序如何影响PriorityQueue中的添加和删除操作

//测试优先级队列
public class a_test_PriorityQueue {
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue(5, new Comparator<Integer>() {
            @Override    //重写的比较 对象的大小发方法 
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });

        queue.add(3);  //乱序添加数据
        queue.add(1);
        queue.add(5);
        queue.add(2);
        queue.add(4);

        while( !queue.isEmpty()){
            Integer m = (Integer) queue.poll();
           System.out.print(m + " ");
        }
    }
}

结果输出，是顺序的，他存入的时候就是顺序的，自己debug 尝试

3. Java PriorityQueue构造函数

PriorityQueue类提供了6种在Java中构造优先级队列的方法。

PriorityQueue（）：使用默认初始容量（11）构造空队列，该容量根据其自然顺序对其元素进行排序。
PriorityQueue（Collection c）：构造包含指定集合中元素的空队列。
PriorityQueue（int initialCapacity）：构造具有指定初始容量的空队列，该容量根据其自然顺序对其元素进行排序。
PriorityQueue（int initialCapacity，Comparator comparator）：构造具有指定初始容量的空队列，该容量根据指定的比较器对其元素进行排序。
PriorityQueue（PriorityQueue c）：构造包含指定优先级队列中元素的空队列。
PriorityQueue（SortedSet c）：构造包含指定有序集合中元素的空队列。

4. Java PriorityQueue方法

PriorityQueue类下面给出了重要的方法，你应该知道。

boolean add（object）：将指定的元素插入此优先级队列。
boolean offer（object）：将指定的元素插入此优先级队列。
boolean remove（object）：从此队列中删除指定元素的单个实例（如果存在）。
Object poll（）：检索并删除此队列的头部，如果此队列为空，则返回null。
Object element（）：检索但不删除此队列的头部，如果此队列为空，则返回null。
Object peek（）：检索但不删除此队列的头部，如果此队列为空，则返回null。
void clear（）：从此优先级队列中删除所有元素。
Comparator comparator（）：返回用于对此队列中的元素进行排序的比较器，如果此队列根据其元素的自然顺序排序，则返回null。
boolean contains（Object o）：如果此队列包含指定的元素，则返回true。
Iterator iterator（）：返回此队列中元素的迭代器。
int size（）：返回此队列中的元素数。
Object [] toArray（）：返回包含此队列中所有元素的数组。

例题： leetcode 23合并K个升序链表

链接：https://leetcode.cn/problems/merge-k-sorted-lists

解决：

    //1.使用队列，可比较性的队列，先得到所有的元素在 队列中，然后再去添加到链表
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue =  //这是一种优先队列的方式 （具有优先级）
                new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
                    @Override  //重写的比较的方法 ，表示队列元素是可以比较的
                    public int compare(ListNode o1, ListNode o2) {
                        if (o1.val < o2.val) return -1;
                        else if (o1.val == o2.val) return 0;
                        else return 1;
                    }
                });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node : lists) {  //把k 个链表 都放入队列中
            if (node != null) queue.add(node);
        }
        while (!queue.isEmpty()) { //再从队列中 出元素，
            ListNode minNode = queue.poll();  //得到一个小元素
            p.next=minNode;  //p 则执行这个小元素
            p = minNode;  //p 向后移动
            if (minNode.next!=null){
                queue.add(minNode.next);
            }

        return dummy.next;
    }