网站建设服务收费标准,中国进入全国紧急状态,游戏网站 模板,中企动力科技股份有限公司沈阳分公司一、PriorityQueue java中提供了两种优先级队列#xff1a;PriorityQueue 和 PriorityBlockingQueue。其中 PriorityQueue 是线程不安全的#xff0c;PriorityBolckingQueue 是线程安全的。 PriorityQueue 使用的是堆#xff0c;且默认情况下是小堆——每次获取到的元素都是…一、PriorityQueue java中提供了两种优先级队列PriorityQueue 和 PriorityBlockingQueue。其中 PriorityQueue 是线程不安全的PriorityBolckingQueue 是线程安全的。 PriorityQueue 使用的是堆且默认情况下是小堆——每次获取到的元素都是最小的元素。 1. 使用方法
1导入包 import java.util.PriorityQueue
2要求传入的元素具备比较大小的能力Comparable | Comparator
3不能传入 null否则会抛出NullPointerException异常
4因为默认为小堆所以优先级最高的元素为最小的元素。若希望优先级最高的元素为最大的元素则需要使用大堆即需要用户提供比较器。将比较器对象作为参数传入其构造函数
2. 内部方法
1构造方法 PriorityQueue创建一个空的优先级队列默认容量为11 PriorityQueueint initialCapacity创建一个初始容量为 initialCapacity 的优先级队列 PriorityQueueCollection? extends E c用一个集合来创建优先级队列 如PriorityQueueInteger q new PriorityQueue(list); 2常用方法 ① boolean offerE 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 ComparatorInteger {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];}ComparatorInteger c new IntegerComparator();PriorityQueueInteger 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);}}
}
