Java中PriorityQueue实现最小堆和最大堆的用法
作者:笨手笨脚° 发布时间:2022-03-25 14:32:18
一、基本介绍
1、介绍
学习很多算法知识,力争做到最优解的学习过程中,很多时候都会遇到PriorityQueue(优先队列)。一个基于优先级堆的 * 优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象,这样做可能导致 ClassCastException。
此队列的头是按指定排序方式确定的最小元素。如果多个元素都是最小值,则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。优先级队列是 * 的,但是有一个内部容量,控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素,其容量会自动增加。无需指定容量增加策略的细节。
此类及其迭代器实现了Collection和Iterator接口的所有可选方法。方法 iterator() 中提供的迭代器不保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历,请考虑使用 Arrays.sort(pq.toArray())。此实现不是同步的,如果多个线程中的任意线程修改了队列,则这些线程不应同时访问PriorityQueue实例。相反,请使用线程安全的PriorityBlockingQueue 类。
PriorityQueue翻译为优先队列,“优先”指元素在队列中按一定的顺序(优先级)进行存放,“队列”指一种先进先出的数据结构。因此PriorityQueue可以实现按照一定的优先级存取元素。
2、用法
从源码来看PriorityQueue的构造方法:
//默认容量为 11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//1、无参构造,默认容量和默认排序方法
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
//2、指定容量
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
//3、指定排序方法
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
//4、指定容量和排序方法
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
由上可知,在构造PriorityQueue时我们可以指定初始容量和元素在队列中的排序方法,若不指定,则默认初始容量为11,默认排序方法为将元素从小到大进行排序。
3、最小堆
构造最小堆:
PriorityQueue<Integer> minheap = new PriorityQueue<>();
使用无参构造,元素在队列中默认按照从小到大的顺序排列,可保证每次出队列的元素为队列中的最小元素。
4、最大堆
PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder());
将排序方法指定为反序,即元素从大到小排列,可保证每次出队列的元素为队列中最大的元素。
5、其他优先级
按照其他优先级规则排序,需要自己实现Comparable接口,重写compareTo()方法。
Comparable<Integer> comparable = new Comparable<Integer>() {
@Override
public int compareTo(Integer o) {
return 0;
}
};
二、常用方法
以Integer类型为例:
三、相关练习题
【剑指 Offer 40. 最小的k个数】
输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
示例 1:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:
输入:arr = [0,1,2,1], k = 1
输出:[0]
限制:
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
【解题思想】
先将k个数放进最大堆,再从第k+1个数开始比较,若其小于大堆顶则加入堆,堆顶出队列,若大于等于则无作为。
【代码】
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int res[] = new int[k];
int len = arr.length;
if(len == 0 || k == 0)
return res;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for(int i = 0; i < k; i++){
maxHeap.add(arr[i]);
}
for(int i = k; i < len; i++){
if(arr[i] < maxHeap.peek()){
maxHeap.add(arr[i]);
maxHeap.poll();
}
}
for(int i = 0; i < k; i++){
res[i] = maxHeap.poll();
}
return res;
}
}
时间复杂度:O(nlogn)
来源:https://blog.csdn.net/qq_43424037/article/details/118266698
猜你喜欢
- 本文实例为大家分享了C语言实现扫雷游戏的具体代码,供大家参考,具体内容如下前言一、游戏规则介绍扫雷是一个十分经典的游戏,一张棋盘中有很多个不
- Java中有哪些队列ArrayBlockingQueue 使用ReentrantLockLinkedBlockingQueue 使用Reen
- 1. JSCH简介JSch 是SSH2的一个纯Java实现。它允许你连接到一个sshd 服务器,使用端口转发,X11转发,文件传输等等。你可
- 此篇文章内容仅限于 描述 thy3.0 自定义标签的说明,所以你在看之前,请先会使用它。直奔主题,以下代码是如何引用 第三方标签的。说明:
- springboot集成开发实现商场秒杀加入主要依赖<dependency> <groupId>org.spring
- 问题用过storm或者jstorm的都知道,如果在bolt代码中发生了没被catch住的异常,所在worker进程会退出。本文就从源码角度分
- 本篇紧接上一篇内容继续,还是从继承里的细节开始1.代码块初始化关于代码块的定义和使用因为之前已经进行过介绍,所以这里就不再赘述,我们所关注的
- java缓冲流本身不具IO功能,只是在别的流上加上缓冲提高效率,像是为别的流装上一种包装。当对文件或其他目标频繁读写或操作效率低,效能差。这
- 一、Rxjava使用场景为了模拟实际场景,从wanandroid网站找了二个接口,如下:(对Wanandroid表示感谢!)public i
- 若代理类在程序运行前就已经存在,那么这种代理方式被成为 静态代理 ,这种情况下的代理类通常都是我们在Java代码中定义的。 通常情况下, 静
- @Order控制配置类/AOP/方法/字段的加载顺序1.AOP加载顺序 @Component &nbs
- 本文实例为大家分享了java简单实现斗地主发牌的具体代码,供大家参考,具体内容如下问题:参考斗地主的游戏规则,完成一个发牌的功能(54张牌,
- 本文实例为大家分享了java实现鲜花销售系统的具体代码,供大家参考,具体内容如下一、练习目标1.体会数组的作用2.找到分层开发的感觉3.收获
- 这里使用的是dynamic-datasource-spring-boot-starter ,它是一个基于springboot的快速集成多数据
- String类型小数值转为Long类型数值分为小数和整数,当传入的类型为String,需要获取的类型为Long,这时候直接通过Long.va
- 为什么Android要申请权限简单说下在Android6.0及6.0以上一些google认为涉及“危险和用户隐私”的一些权限不仅要做清单文件
- WebMvcConfigurer配置类其实是Spring内部的一种配置方式,采用JavaBean的形式来代替传统的xml配置文件形式进行针对
- 背景今天面试字节算法岗时被问到的问题,让我用C++实现一个softmax函数。softmax是逻辑回归在多分类问题上的推广。大概的公式如下:
- 自定义工具类PropertyUtil,并在该类的static静态代码块中读取properties文件内容保存在static属性中以供别的程序
- 前言:mongodb是一个基于分布式文件存储的开源数据库系统。mongodb与我们平常使用的mysql的区别: 1.