目录

        关于PriorityQueue的使用注意：

        1.使用时必须导入 PriorityQueue 所在的包：

        2.PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常

      3.不能插入 null 对象，否则会抛出NullPointerException

      4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容。

         5.PriorityQueue底层使用了堆数据结构，默认情况下是小堆---即每次获取到的元素都是最小的元素。

        PriorityQueue优先级队列的构造：

        第一种：

         第二种：

        建立大根堆的PriorityQueue

        PriorityQueue优先级队列的方法：

不同阶段的扩容规则

1. 容量小于 64 时

2. 容量大于等于 64 时

3. 容量超过 MAX_ARRAY_SIZE 时

        top-k问题：最大或者最小的前k个数据。

      方法一（利用PriorityQueue优先级队列）：

     方法二（建立大小为k的大根堆）：

        获取前k个最小的数：题目链接

---

         Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列， PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。

        这里我们主要介绍PriorityQueue：

        关于PriorityQueue的使用注意：

        1.使用时必须导入 PriorityQueue 所在的包：

import java.util.PriorityQueue;

        2.PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常

        PriorityQueue 要求元素能够比较大小，是为了实现其内部的排序功能，确保每次取出的元素都是优先级最高的元素。

      3.不能插入 null 对象，否则会抛出NullPointerException

      4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容。

         5.PriorityQueue底层使用了堆数据结构，默认情况下是小堆---即每次获取到的元素都是最小的元素。

        

        

        PriorityQueue优先级队列的构造：

        第一种：

// 创建⼀个空的优先级队列，底层默认容量是 11 PriorityQueue<Integer> q1 = new PriorityQueue<>();

         第二种：

// 创建⼀个空的优先级队列，容量为aPriorityQueue<Integer> q2 = new PriorityQueue<>(a);

        注意：a不能小于1，否则会抛异常。

        

        

        建立大根堆的PriorityQueue

         由于在默认情况下 PriorityQueue 队列是小根堆，如果需要大根堆需要提供比较器：

// ⽤⼾⾃⼰定义的⽐较器：直接实现Comparator接⼝，然后重写该接⼝中的compare⽅法即可
class IntCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}

         IntCmp 是比较器类名。

        

        对比：

        默认情况下的小根堆：

 PriorityQueue<Integer> p1 = new PriorityQueue<>();p1.offer(6);p1.offer(10);p1.offer(5);p1.offer(8);System.out.println(p1.peek());

程序运行结果：

        

         使用了比较器创建的大根堆：

class MaxC implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}public class Test {public static void main(String[] args) {PriorityQueue<Integer> p1 = new PriorityQueue<>(new MaxC());p1.offer(6);p1.offer(10);p1.offer(5);p1.offer(8);System.out.println(p1.peek());}
}

        程序运行结果：

        

         

        

        PriorityQueue优先级队列的方法：

        

         

        

        

不同阶段的扩容规则

1. 容量小于 64 时

当队列当前容量（即底层数组的长度）小于 64 时，每次扩容会将容量扩展为原来的 2 倍。例如，初始容量为 16，当元素数量超过 16 时，队列会进行扩容，新的容量变为 16 * 2 = 32；若再次触发扩容，容量会变为 32 * 2 = 64。

2. 容量大于等于 64 时

当队列当前容量大于等于 64 时，每次扩容会将容量扩展为原来的 1.5 倍。例如，当容量达到 64 并触发扩容时，新的容量变为 64 + 64 / 2 = 96。

3. 容量超过 MAX_ARRAY_SIZE 时

MAX_ARRAY_SIZE 是一个预定义的最大数组长度限制。当按照上述规则计算得到的新容量超过这个限制时，会将容量设置为 MAX_ARRAY_SIZE。这是为了避免创建过大的数组，防止出现内存溢出等问题。

        

        top-k问题：最大或者最小的前k个数据。

         这里我们解决的是前k个最小的数据。

        假如给出一个数组，取出数组 k 个最小的个元素。

      方法一（利用PriorityQueue优先级队列）：

        代码实现：

 public static int[] topk1(int[] array,int k) {PriorityQueue<Integer> p1 = new PriorityQueue<>();for (int i = 0; i < array.length; i++) {p1.offer(array[i]);}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = p1.poll();}return ret;}public static void main(String[] args) {int[] array = {1,12,3,41,5,16,7,81,9,10};int[] ret = topk1(array, 5);System.out.println(Arrays.toString(ret));}

        代码运行结果：

        

         

        

     方法二（建立大小为k的大根堆）：

        代码实现：

class ImpLess implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}public class Test {public static int[] topk(int[] array,int k) {PriorityQueue<Integer> p1 = new PriorityQueue<>(k,new ImpLess());for (int i = 0; i < k; i++) {p1.offer(array[i]);}for (int i = k; i < array.length; i++) {if(p1.peek() > array[i]) {p1.poll();p1.offer(array[i]);}}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = p1.poll();}return ret;}public static void main(String[] args) {int[] array = {1,12,3,41,5,16,7,81,9,10};int[] ret = topk(array, 5);System.out.println(Arrays.toString(ret));}
}

        运行结果：

        

         可以看到，结果也是正确的。

        分析：

        我们建立了一个大小为k的大根堆，先拿数组前k个元素插入堆里，由于建立的是大根堆，堆顶元素是最大的，那么只要遍历剩余的数组元素并于堆顶元素比较，如果堆顶元素比数组元素大了，删除堆顶元素，PriorityQueue会自动向下调整，之后还是大根堆，依次遍历完数组，就能得到k个最小的元素了。

        方法二也是优解。

        

        获取前k个最小的数：题目链接

        这题的思路与上面两个方法逻辑是一样的。 

        题解代码：

class Imbig implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}class Solution {public int[] smallestK(int[] arr, int k) {int[] array = new int[k];if(k <= 0) {return array;}PriorityQueue<Integer> list = new PriorityQueue<>(new Imbig());for (int i = 0; i < k; i++) {list.offer(arr[i]);}for(int i = k;i < arr.length;i++) {int count = list.peek();if(count > arr[i]) {list.poll();list.offer(arr[i]);}}for (int i = 0; i < k; i++) {array[i] = list.poll();}return array;}}