优先队列PriorityQueue用法：小顶堆与重写大顶堆，以及具体示例leetcode23. 合并 K 个升序链表_优先队列默认是小顶堆吗

 1、概括       

        在数据结构中，存在一种高效的双向队列PriorityQueue。

        它可以实现排序、调度和管理元素等功能。相对于普通的队列和栈等数据结构，PriorityQueue有以下几个优点：

1. 内部实现使用二叉堆或者Fibonacci堆等高效数据结构，因此插入和删除操作的时间复杂度为 O(log n)，查找最小元素的时间复杂度为 O(1)。

2. PriorityQueue 具有自动按照元素优先级排序的特性，每次取出元素的时候都是最大或最小的。在进行多次排序操作的时候，可以节省大量的时间和空间。

3. PriorityQueue的容量是自动扩充的，因此无需手动进行调整，可以方便地存储任意数量的元素。

4. PriorityQueue支持可重复元素，即队列中可以存放相同元素。

        其中的第2点，该性质经常被用于算法题中，自动筛选批量数据的最小值。比方说，直接将一个list的元素全都入栈优先队列，那么每次调用pop，出栈的都是该队列的最小值。 

---

2、使用方法 

2.1 默认整型情况

        默认实现为小顶堆，可以理解为，每次pop出的元素都为最小。
        实现方法：

PriorityQueue<Integer> queue = new PriorityQueue<>();

2.2 比较多种类型的元素时的情况

例1

        例如，如果我们想比较出一系列数组中每个数组下标为“1”的元素大小，即，每次pop出最小的这种元素，该怎么办呢？见以下代码：其原理见第3节

PriorityQueue<int []> queue = new PriorityQueue<>(
        new Comparator<int[]>(){
            public int compare(int m[], int n[]){
                return m[1] - n[1];
            }
        }); 

        使用Lambda表达式后的代码如下：

PriorityQueue<int[]> queue = new PriorityQueue<>((m, n) -> m[1] - n[1]);

        在这段代码中，int[]是指定了队列元素的数据类型。这里使用了泛型，即在定义队列时可以指定元素的数据类型。在这个例子中，指定了队列中存储元素的数据类型为整型数组(int[])类型。

        如果你想存储其他类型的对象，只需要将int[]替换成对应的类型即可。例如，如果你想存储字符串类型的对象，则可以使用以下代码：

例2 

PriorityQueue<String> queue = new PriorityQueue<>(new Comparator<String>() {
    public int compare(String m, String n){
        return m.length() - n.length();
    }
});

         这里是指定队列元素的数据类型为字符串(String)类型，并且通过比较器将字符串按照长度从小到大进行排序。因此，在使用优先队列时，需要根据实际需要指定相应的元素类型。

2.3 重写为大顶堆

        如果想每次输出权重最大，而非最小的元素，该怎么办呢？

        只需要在重写compare方法时调换两个元素的位置即可。例如lambda表达式：

PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1)

和

PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o1 - o2)

是有区别的！

        这两行代码都实例化了一个优先队列，存储的元素为整型(Integer)类型。二者在Lambda表达式中指定排序规则的方式不同。

        第一行代码(o1,o2) -> o2 - o1表示按照从大到小的顺序进行排序，即将第二个参数o2减去第一个参数o1，排序后结果为逆序排列。（大顶堆）

        而第二行代码(o1,o2) -> o1 - o2表示按照从小到大的顺序进行排序，即将第一个参数o1减去第二个参数o2，排序后结果为正序排列。（默认小顶堆）

        因此，二者在排序结果上是完全相反的。选用哪一种方式应该根据具体的应用场景及排序要求来选择。

---

3、实现原理

        在源码中，PriorityQueue构造器里可以传入Comparator接口的匿名内部类对象。如果传入该对象，就要重写其compare方法，实现比较大小。

public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

int compare(T o1, T o2); 

---

4、应用：leetcode23. 合并 K 个升序链表

        现在你已经掌握了优先队列的用法了，尝试解决一个简单的问题吧！

         

 

解题方法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //每次比较的是该节点的值，重写compare：
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>((o1,o2) -> o1.val - o2.val);
        //将需要比较的全部链表头节点加入
        for(ListNode node : lists){
            if(node != null){
               pq.add(node); 
            }
        }
        //构建head空节点，方便返回链表
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while(!pq.isEmpty()){
            ListNode cur = pq.poll();//每一轮都出栈最小的
            tail.next = cur;
            tail = tail.next;
            if(cur.next != null){
                pq.add(cur.next);
            }
        }
        return head.next;
    }
}