优先级队列（PriorityQueue 和 Top-K问题）

一、PriorityQueue

  java中提供了两种优先级队列：PriorityQueue 和 PriorityBlockingQueue。其中 PriorityQueue 是线程不安全的，PriorityBolckingQueue 是线程安全的。

  PriorityQueue 使用的是堆，且默认情况下是小堆——每次获取到的元素都是最小的元素。

  

1. 使用方法

（1）导入包： import java.util.PriorityQueue

（2）要求传入的元素具备比较大小的能力：Comparable | Comparator

（3）不能传入 null，否则会抛出NullPointerException异常

（4）因为默认为小堆，所以优先级最高的元素为最小的元素。若希望优先级最高的元素为最大的元素，则需要使用大堆，即需要用户提供比较器。（将比较器对象作为参数传入其构造函数）

2. 内部方法：

（1）构造方法：

PriorityQueue（）：创建一个空的优先级队列，默认容量为11

PriorityQueue（int  initialCapacity）：创建一个初始容量为 initialCapacity 的优先级队列

PriorityQueue（Collection<? extends E>  c）：用一个集合来创建优先级队列

如：PriorityQueue<Integer> q = new PriorityQueue<>(list);

（2）常用方法：

① boolean offer（E  e）：插入元素 e   O(log(n))

② E peek（）：获取优先级最高的元素，若优先级队列为空，返回null

③ E poll（）：删除优先级最高的元素并将其返回，若队列为空，返回null    O(log(n))

④ int  size（）：获取有效元素的个数

⑤ void clear（）：清空

⑥ boolean  isEmpty（）：判断优先级队列是否为空

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

• 当容量小于 64 时，按照 oldCapacity 的 2 倍扩容
• 当容量大于 64 时，按照 oldCapacity 的 1.5 倍扩容
• 当容量超过 MAX_ARRAY_SIZE 时，按照 MAX_ARRAY_SIZE 扩容

二、Top-K问题   

  Top-K问题：在一组数据中，找到最大（最小）的 K 个数。

  不需要对所有数据进行排序，只需要找到符合要求的 K 个数，然后将这 K 个数再进行排序。

  如何用堆去解决 Top-K 问题：

假设要在海量数据中找到最大的 K 个数：

（1）要找最大的：建小堆。（因为后序需要用堆顶元素跟其他元素进行比较）

（2）该小堆的最大容量为 K

（3）把剩下的元素挨个和堆顶元素（K个中最小的）进行比较

如果 元素 <= 堆顶元素 ： 该元素一定不是最大个K个元素中的元素

如果 元素 > 堆顶元素 ：该元素是候选人，用该元素替代堆顶元素 + 向下调整。

  代码的实现可以分两种：直接使用 PriorityQueue 优先级队列、不使用 PriorityQueue 即自己实现其内部的堆。

面试题 17.14. 最小K个数

代码一：直接使用 PriorityQueue 优先级队列以及删除、添加的方法。

class Solution {//因为最小的 k 个数，所以需要建大堆static class IntegerComparator implements Comparator<Integer> {public int compare(Integer o1, Integer o2) {//重写比大小的规则return o2 - o1;}}public int[] smallestK(int[] arr, int k) {//考虑 k == 0if (k == 0) {return new int[0];}Comparator<Integer> c = new IntegerComparator();PriorityQueue<Integer> p = new PriorityQueue<>(c);//将前 k 个数放入堆中for (int i = 0; i < k; i++) {p.offer(arr[i]);}//将剩下的元素依次和堆顶元素比较//if（元素 >= 堆顶元素）：该元素一定不是前 K 个中的元素//else（元素 < 堆顶元素）：该元素是候选人，用该元素替换堆顶元素 + 向下调整//若使用 PriorityQueue ，直接删除堆顶元素，再将元素加入优先级队列中即可。for (int i = k; i < arr.length; i++) {int e = arr[i];int t = p.peek();if (e < t) {p.poll();p.offer(e);}}//整个过程完成后，优先级队列中保存的就是我们需要的 Top-K （最小的k个数）//因为题目中，需要返回的是一个数组，所以我们定义一个数组存储 k 个元素。int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = p.poll();}return ans;}public void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}

代码二：自己实现优先级队列内部的堆操作（数组）

class Solution {//因为最小的 k 个数，所以需要建大堆public int[] smallestK(int[] arr, int k) {//考虑 k == 0if (k == 0) {return new int[0];}//创建优先级队列 -> 创建一个大堆int[] ans = Arrays.copyOf(arr,k);creatHeap(ans, k);for (int i = k; i < arr.length; i++) {if (arr[i] < ans[0]) {ans[0] = arr[i];adjustDown(ans, k, 0);}}return ans;}//向下调整public static void adjustDown(int[] arr, int size, int index){//1. "我"是否是叶子结点//2. 找到 “我” 的左右孩子中最大的孩子//3. 比较“我”和最大孩子的大小：//    我 < 最大的孩子 ： 交换//    我 >= 最大的孩子： 不进行交换//4. 交换后更新结点继续向下调整（循环）while (index * 2 + 1 < size){int maxIdx = index * 2 + 1;if (maxIdx + 1 < size && arr[maxIdx] < arr[maxIdx + 1]) {maxIdx = maxIdx + 1;}if (arr[index] >= arr[maxIdx]) {break;}//交换int tmp = arr[index];arr[index] = arr[maxIdx];arr[maxIdx] = tmp;index = maxIdx;}}//建大堆//从最后一个有孩子的双亲结点开始,向下调整，依次到根结点。public static void creatHeap(int[] arr, int size){int pIdx = (size - 2)/2;for (int i = pIdx; i >= 0; i--) {adjustDown(arr,size,i);}}
}