背景
开始以为优先级队列，类似于普通队列一样，new之后就可以使用了，加入后的元素会自动实现大顶堆或者小顶堆，其实并不然。
java的优先级队列需要自己实现来定义大顶堆或者小顶堆。
java 的 PriorityQueue 是一个基于优先级堆的队列实现，它支持自然排序和自定义排序两种方式。
当使用自然排序时，队列中的元素必须实现 Comparable 接口，且默认是按照元素的自然顺序排序（即从小到大）。
如果要实现自定义排序，可以通过传入一个 Comparator 对象来实现，Comparator 对象中的 compare方法决定了元素的排序方式。
当元素实现了 Comparable接口时：
- 可以让对象具备默认的自然排序规则，方便直接调用
Collections.sort()等方法进行排序。- 实现Comparable接口的类可以作为集合的元素，使得集合内部的元素能够自动排序。
当元素实现了 Comparator接口时：
- 使用Comparator接口可以根据不同的需求定义多种排序规则。
- 实现Comparator接口的类可以作为参数传递给
Collections.sort()等方法，从而实现定制排序。
具体可以看什么是Comparable和Comparator?
因此，想要实现一个优先级队列，队列元素必须要实现自然排序和自定义排序。
案例
自然排序
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;
}
}
自定义排序
给你一个整数数组 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;
}
}
