当前位置： 首页 > news >正文

【Java 数据结构】PriorityQueue(堆)的使用及源码分析

news 2025/9/1 22:32:53

🎉🎉🎉点进来你就是我的人了
博主主页：🙈🙈🙈戳一戳,欢迎大佬指点!
人生格言：当你的才华撑不起你的野心的时候,你就应该静下心来学习!

欢迎志同道合的朋友一起加油喔🦾🦾🦾
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个🐒嘿嘿
谢谢你这么帅气美丽还给我点赞！比个心

目录

1.PriorityQueue的介绍

2. PriorityQueue的使用

3. PriorityQueue源码剖析

4. Top-K问题

1.PriorityQueue的介绍

PriorityQueue的特性

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

2. 不能 插入 null 对象，否则会抛出 NullPointerException,而Queue是可以插入null的

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

4. 插入和删除元素的时间复杂度为O(log(N))

5. PriorityQueue 底层使用了堆数据结构

6. PriorityQueue 默认情况下是小堆 --- 即每次获取到的元素都是最小的元素

2. PriorityQueue的使用

构造方法

构造方法说明
PriorityQueue()不带参数，默认容量为11
PriorityQueue(int initialCapacity)参数为初始容量，该初始容量不能小于1
PriorityQueue(Collection<? extends E> c)参数为一个集合

  常用方法

方法说明
boolean offer(E e)插入元素e，返回是否插入成功，e为null，会抛异常
E peek()获取堆（后面介绍堆）顶元素，如果队列为空，返回null
E poll()删除堆顶元素并返回，如果队列为空，返回null
int size()获取有效元素个数
void clear()清空队列
boolean isEmpty()判断队列是否为空

第一个构造方法：

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

 第二个构造方法：

// 创建一个空的优先级队列，底层的容量为initialCapacity PriorityQueue<Integer> q2 = new PriorityQueue<>(100);

第三个构造方法：

ArrayList<Integer> list = new ArrayList<>();
list.add(4);
list.add(3);
list.add(2);
list.add(1);// 用ArrayList对象来构造一个优先级队列的对象
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);//此时q3中已经包含了四个元素
System.out.println(q3.size());//4
System.out.println(q3.peek());//1

注意： 默认情况下，PriorityQueue队列是小堆，如果要转换成大堆需要用户提供比较器

class intCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;//大根堆//o2-o1  小根堆}
}
public class PriorityQueueDemo {public static void main(String[] args) {intCmp intcmp = new intCmp();PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(intcmp) ;priorityQueue.offer(4);priorityQueue.offer(3);priorityQueue.offer(2);priorityQueue.offer(1);System.out.println(priorityQueue.peek());//4}
}

也可以用匿名内部类的写法：

    public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}}) ;priorityQueue.offer(12);priorityQueue.offer(2);priorityQueue.offer(80);System.out.println(priorityQueue.peek());//80}

  Lambda表达式写法(推荐使用):

PriorityQueue<Integer> queue = new PriorityQueue<>((o1 , o2) -> o1 - o2); // 小根堆
PriorityQueue<Integer> queue = new PriorityQueue<>((o1 , o2) -> o2 - o1); // 大根堆

3. PriorityQueue源码剖析

  • 使用Student对象来创建一个优先级队列的对象

当我们在priorityQueue中存放一个Student 对象时， 可以正常放入且不发生报错。

但是当我们存放两个Studnet对象时，程序报错，出现类型不兼容异常。

public class TestDemo2 {
//    注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器public static void main(String[] args) {PriorityQueue<Student> priorityQueue = new PriorityQueue<>();priorityQueue.offer(new Student(10));priorityQueue.offer(new Student(5));}}

0fd6bc3220869115d5a5f642df12c894.png​

前边学习抽象类和常用接口时，我们了解到Java中对于引用数据类型的比较或者排序，一般都要用到使用Comparable接口中的compareTo() 方法

此时我们可以实现Comparable接口，并且重写 compare()方法。

class Student implements Comparable<Student>{public int age;public Student(int age) {this.age = age;}@Overridepublic int compareTo(Student o) {return this.age - o.age;}
}
public class TestDemo2 {
//    注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器public static void main(String[] args) {PriorityQueue<Student> priorityQueue = new PriorityQueue<>();priorityQueue.offer(new Student(10));priorityQueue.offer(new Student(5));}
}

经过调试我们可以发现，此时优先级队列中的两个元素已经按照小根堆的方式调整好了。

0653d9fc42d8553548acd28d50532eff.png​

那么PriorityQueue是怎么对其中的引用数据类型进行调整的呢？

2d3e2a7b2e1e046a782af4fedd17603b.png​

使用this引用指向了下边的方法，并传递参数。

0f5d46ef235c34074818ef17e04e6860.png​

当queue数组初始化完毕时， 需要向数组中存放元素，即进行 priorityQueue.offer(new Student(10));

a357ae03bff5a5a7d9daf181f1827bde.png​

存放第二个元素时，i = 1 , size = 2 ,则需要执行 siftUp(1 , e) ,对 元素进行向上调整为小根堆 。

41bcef9cd1147433157d48a662ee4046.png​

向下调整的过程中，使用了我们所重写的compareTo()方法，然后判断e,key对应的age的值，进行交换，如果此处不需要交换，则直接将key放入queue[1] 中即可 ， 此时，小根堆调整完成

fa67bcbb6cda9b6154bf8058f573602b.png​

如果想要调整为大根堆的话，只需要修改Student类中的compareTo()方法即可

class Student implements Comparable<Student>{public int age;public Student(int age) {this.age = age;}@Overridepublic int compareTo(Student o) {return this.age - o.age;}
}
public class TestDemo2 {
//    注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器public static void main(String[] args) {PriorityQueue<Student> priorityQueue = new PriorityQueue<>();priorityQueue.offer(new Student(10));priorityQueue.offer(new Student(5));}
}

cdb19d71f069688b738c505600307695.png​

那么Integer类型的参数该如何修改为大根堆 呢？ ，Integer类型已经重写了compareTo方法，但是已经写死了，默认为小根堆的实现方式，无法修改源码，此时，我们就应该 构造Comparator 比较器来实现。

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{ 
@Override
public int compare(Integer o1, Integer o2) { //return o2-o1;return o2.compareTo(o1);} 
}
public class TestPriorityQueue {public static void main(String[] args) { PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp()); p.offer(4);p.offer(3); p.offer(2);p.offer(1);p.offer(5);}
}

❗当传入比较器时，PriorityQueue会按照 比较器的方式进行 比较，与实现Comparable 接口的方法类似，此处不再赘述，元素进而被调整为大根堆。

d87918ed651e195c24dd8e6cfffd5168.png​

91906c6bcaf27804ca71635b89eeda96.png​

✅另一种写法 ：

public class TestPriorityQueue {public static void main(String[] args) { //匿名内部类，这里有一个类，实现了Comparator 这个接口，并重写了compare这个方法PriorityQueue<Integer> p = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) { return o2 - o1;}});}
}

🔻PriorityQueue的扩容机制：

c84109602dae041fefbc39e611c8a472.png​

优先级队列的扩容说明：

  • 如果容量小于64时，是按照约oldCapacity的2倍方式扩容的（2*OldCapacity+2）

  • 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的

  • 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

4. Top-K问题

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

      1. 用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

      2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

为什么建小堆可以求出前k个最大元素呢?(求大根堆同理)

我们可以这样来理解,最开始我们拿数组的前k个元素建立成小堆,那么此时堆顶元素一定是前k个元素中的最小值数组,那此时我们剩下的元素与堆顶元素比较时,如果比堆顶元素还小,那么它一定不是前k个中的最大值,当数组元素大于堆顶元素时,这个值可能是要求的最大值,我们删除堆顶元素添加这个值,重新调整为小根堆,重复上述操作,最后小根堆里面就是我们要求的最大值.

class Solution {public int[] smallestK(int[] arr, int k) {int[] vec = new int[k];if (vec == null || k == 0) {return vec;}//传入比较器，按照大根堆调整PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {public int compare(Integer num1, Integer num2) {return num2 - num1;}});//存入K个 元素for (int i = 0; i < k; ++i) {queue.offer(arr[i]);}//比较堆顶元素与剩余n - k个元素的值的大小//如果堆顶元素较大，则弹出堆顶，重新调整，元素入堆for (int i = k; i < arr.length; ++i) {if (queue.peek() > arr[i]) {queue.poll();queue.offer(arr[i]);}}//将堆中元素存入数组中for (int i = 0; i < k; ++i) {vec[i] = queue.poll();}return vec;}}

​

http://www.lryc.cn/news/61613.html

相关文章：

  • 使用 Kubernetes 运行 non-root .NET 容器
  • 为什么大量失业集中爆发在2023年？被裁？别怕！失业是跨越职场瓶颈的关键一步！对于牛逼的人，这是白捡N+1！...
  • Word控件Spire.Doc 【脚注】字体(3)：将Doc转换为PDF时如何使用卸载的字体
  • keil5使用c++编写stm32控制程序
  • 中国社科院与美国杜兰大学金融管理硕士项目——在职读研的日子里藏着我们未来无限可能
  • hardhat 本地连接matemask钱包
  • 【华为OD机试真题】1001 - 在字符串中找出连续最长的数字串含-号（Java C++ Python JS）| 机试题+算法思路+考点+代码解析
  • CrackMapExec 域渗透工具使用
  • Modbus协议学习
  • camunda如何处理流程待办任务
  • git部分文件不想提交解决方案
  • 2023年全国最新道路运输从业人员精选真题及答案58
  • Zimbra 远程代码执行漏洞(CVE-2019-9670)漏洞分析
  • 【数据结构初阶】第七节.树和二叉树的性质
  • 车载软件架构——闲聊几句AUTOSAR BSW（一）
  • 我国元宇宙行业分析：政策、技术、资金助推行业探索多元化应用场景
  • 都已经那么卷了，用户还需要开源的 API 管理工具么
  • 工信部教育与考试中心-软件测试工程师考试题A卷-答
  • 【设计模式】模板方法模式--让你的代码更具灵活性与可扩展性
  • 搞明白Redis持久化机制
  • C# 中的正则表达式，如何使用正则表达式进行字符串匹配和替换？
  • 7年时间，从功能测试到测试开发月薪30K，有志者事竟成
  • ES6 块级作用域
  • ShardingSphere-JDBC垂直分片
  • Node 04-http模块
  • 记录项目过程中的编译错误及解决方法（持续更新中）
  • Android Hilt依赖注入框架
  • LeetCode：59. 螺旋矩阵 II
  • 信息安全复习六：公开密钥密码学
  • YOLOv8 更换主干网络之 ShuffleNetv2