背景

开始以为优先级队列，类似于普通队列一样，new之后就可以使用了，加入后的元素会自动实现大顶堆或者小顶堆，其实并不然。

java的优先级队列需要自己实现来定义大顶堆或者小顶堆。

java 的 PriorityQueue 是一个基于优先级堆的队列实现，它支持自然排序和自定义排序两种方式。

当使用自然排序时，队列中的元素必须实现 Comparable 接口，且默认是按照元素的自然顺序排序（即从小到大）。

如果要实现自定义排序，可以通过传入一个 Comparator 对象来实现，Comparator 对象中的 compare方法决定了元素的排序方式。

因此，想要实现一个优先级队列，队列元素必须要实现自然排序和自定义排序。

案例

自然排序

23. 合并 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 {
    //定义一个NodeSort类，用于优先级队列元素，该类型定义的是一个小顶堆结构
    //该类有俩个元素，nodeValue该元素用于排序，node元素为ListNode类型，通过node.next可找到链表的下个元素
    class NodeSort implements Comparable<NodeSort>{
        int nodeValue;
        ListNode node;
        public NodeSort(int nodeValue,ListNode node){
            this.nodeValue = nodeValue;
            this.node = node;
        }
        @Override
        //自定义元素排序，使用nodeValue进行比较，
        //this.nodeValue - o.nodeValue表示按照nodeValue升序排列，也就是定义一个小顶堆
        public int compareTo(NodeSort o) {
            return this.nodeValue - o.nodeValue;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        //实现一个优先级队列，本优先级队列使用的是自然排序的方式构建优先级队列，
        //存储NodeSort类型的元素，且该优先级队列为一个小顶堆结构
        PriorityQueue<NodeSort> nodeQueue = new PriorityQueue<>();
        //先将k个链表的第一个节点都加入小顶堆，堆顶元素为队列中元素的最小值
        for (int i=0;i<lists.length;i++){
            if(lists[i] != null){
                nodeQueue.offer(new NodeSort(lists[i].val,lists[i]));
            }
        }
        ListNode head = new ListNode();
        ListNode tail = head;
        while (nodeQueue.size() !=0){
            //poll出堆顶元素表示最小元素
            NodeSort smallNode = nodeQueue.poll();
            tail.next = smallNode.node;
            tail = smallNode.node;
            //如果smallNode处于某个链表的最末端了，则下个元素为Null了，则不需要继续offer了
            if(smallNode.node.next !=null){
                //如果smallNode.node节点被poll出了说明该节点是队列元素中最小的，则需要将smallNode.node.next加入到队列在进行比较
                //这里原理如果不懂的话，可以看21题很相似（合并两个有序链表）
                nodeQueue.offer(new NodeSort(smallNode.node.next.val,smallNode.node.next));
            }
        }
        return head.next;
    }
}

自定义排序

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0){
            return null;
        }
        //定义一个优先队列(大顶堆)
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //表示按照数组中的下标0元素自大到小排序
                return o2[0] - o1[0];
            }
        });
        //初始化一个数组
        int[] ret = new int[nums.length-k+1];
        //先将第一个窗口内的所有元素都入队，对顶元素即为最大值
        for (int i=0;i<k;i++){
            //入队尾
            queue.offer(new int[]{nums[i],i});
        }
        int cnt =0;
        ret[cnt] = queue.peek()[0];
        //从窗口的右侧下标开始遍历，直到数组末尾
        for (int i=k;i<nums.length;i++){
            //将元素入队
            queue.offer(new int[]{nums[i],i});
            //此时有个问题，堆顶的元素可能已经是窗口之外的元素了，因为窗口是右移，所以窗口之外的元素肯定是左侧的元素了
            // 所以怎么判断是窗口之外的元素呢？
            //窗口有大小，且右下标为i,做下标为i-k+1,所以如果堆顶的最大元素小于等于i-k的元素就肯定是窗口之外的元素，直接poll即可。
            while (queue.peek()[1]<=i-k){
                //出队首
                queue.poll();
            }
            ret[++cnt] =queue.peek()[0];
        }
        return ret;
    }

}