优先级队列(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);}}
}
相关文章:

优先级队列(PriorityQueue 和 Top-K问题)
一、PriorityQueue java中提供了两种优先级队列:PriorityQueue 和 PriorityBlockingQueue。其中 PriorityQueue 是线程不安全的,PriorityBolckingQueue 是线程安全的。 PriorityQueue 使用的是堆,且默认情况下是小堆——每次获取到的元素都是…...

计算机组成与设计04——处理器
系列文章目录 本系列博客重点在深圳大学计算机系统(3)课程的核心内容梳理,参考书目《计算机组成与设计》(有问题欢迎在评论区讨论指出,或直接私信联系我)。 第一章 计算机组成与设计01——计算机概要与技…...

IT行业那么辛苦,我们为什么还要选择它?
疫情三年,我们学会了什么?工作诚可贵,技能价更高。 搞IT辛苦?有啥辛苦的?说什么辛苦?能有工作,工资又高,还要什么自行车,有啥搞啥吧!每次看到网络上有人问有…...
PyTorch学习笔记:nn.CrossEntropyLoss——交叉熵损失
PyTorch学习笔记:nn.CrossEntropyLoss——交叉熵损失 torch.nn.CrossEntropyLoss(weightNone, size_averageNone, ignore_index-100, reduceNone, reductionmean, label_smoothing0.0)功能:创建一个交叉熵损失函数: l(x,y)L{l1,…,lN}T&…...
【VictoriaMetrics】什么是VictoriaMetrics
VictoriaMetrics是一个快速、经济、可扩展的监控解决方案和时间序列数据库,有单机版和集群版本,基础功能及集群版本基本功能不收费,VictoriaMetrics有二进制安装版本、Docker安装版本等多种安装方式,其源码及部署包更新迭代很快,VictoriaMetrics具有以下突出特点: 它可以作…...

(第五章)OpenGL超级宝典学习:统一变量(uniform variable)
统一变量 前言 本篇在讲什么 本篇记录对glsl中的变量uniform的认知和学习 本篇适合什么 适合初学Open的小白 适合想要学习OpenGL中uniform的人 本篇需要什么 对C语法有简单认知 对OpenGL有简单认知 最好是有OpenGL超级宝典蓝宝书 依赖Visual Studio编辑器 本篇的特色 …...

数据存储技术复习(四)未完
1.什么是NAS。一般用途服务器与NAS设备之间有何不同。NAS是一个基于IP的专用高性能文件共享和存储设备。—般用途服务器可用于托管任何应用程序,因为它运行的是一般用途操作系统NAS设备专用于文件服务。它具有专门的操作系统,专用于通过使用行业标准协议…...

Rust编码的信息窃取恶意软件源代码公布,专家警告已被利用
黑客论坛上发布了一个 用Rust编码的信息窃取恶意软件源代码 ,安全分析师警告,该恶意软件已被积极用于攻击。 该恶意软件的开发者称,仅用6个小时就开发完成,相当隐蔽, VirusTotal的检测率约为22% 。 恶意软件开发者在…...
diffusers编写自己的推理管道
英文文献:Stable Diffusion with 🧨 Diffusers 编写自己的推理管道 最后,我们展示了如何使用diffusers. 编写自定义推理管道是对diffusers库的高级使用,可用于切换某些组件,例如上面解释的 VAE 或调度程序。 例如&a…...

计算机操作系统 左万利 第二章课后习题答案
计算机操作系统 左万利 第二章课后习题答案 1、为何引进多道程序设计,在多道程序设计中,内存中作业的道数是否越多越好?说明原因。 引入多道程序设计技术是为了提高计算机系统资源的利用率。在多道程序系统中,内存中作业的道数并…...

CODESYS开发教程10-文件读写(SysFile库)
今天继续我们的小白教程,老鸟就不要在这浪费时间了😊。 前面一期我们介绍了CODESYS的文件操作库CAA File。这一期主要介绍CODESYS的SysFile库所包含的文件读写功能块,主要包括文件路径、名称、大小的获取以及文件的创建、打开、读、写、拷贝…...

Linux安装redis
Linux安装redis一.下载二.解压配置1.创建文件夹2.上传文件3.解压4.编译配置三.启动测试1.启动2.防火墙配置3.测试四.设置开机自启1.配置脚本2.添加服务3.测试一.下载 redis官网:https://redis.io/ redis官方下载地址:http://download.redis.io/releases…...

计算机组成与体系结构 性能设计 William Stallings 第2章 性能问题
2.1 优化性能设计例如,当前需要微处理器强大功能的桌面应用程序包括:图像处理、三维渲染、语音识别、视频会议、多媒体创作、文件的声音和视频注释、仿真建模从计算机组成与体系结构的角度来看,一方面,现代计算机的基本组成与50多…...

anaconda详细介绍、安装及使用(python)
anaconda详细介绍、安装及使用1 介绍1.1 简介1.2 特点1.3 版本下载2 Anaconda管理Python包命令3 安装3.1 windows安装4 操作4.1 Conda 操作4.2 Anaconda Navigator 操作4.3 Spyder 操作4.4 Jupyter Notebook 操作5 示例参考1 介绍 1.1 简介 Anaconda是用于科学计算(…...

雅思经验(6)
反正我是希望遇到的雅思听力section 4.里面填空的地方多一些,之后单选的部分少一些。练了一下剑9 test3 的section 4,感觉还是不难的,都是在复现,而且绕的弯子也不是很多。本次考试的目标就是先弄一个六分,也就是说&am…...
CentOS9源码编译libvirtd工具
卸载原有版本libvirt [rootcentos9 ~]# yum remove libvirt Centos9配置网络源 [rootcentos9 ~]# dnf config-manager --set-enabled crb [rootcentos9 ~]# dnf install epel-release epel-next-release 安装依赖包 [rootcentos9 ~]# yum install -y libtirpc-devel libxml2-de…...
搭建内网穿透
文章目录摘要npsfrp服务提供商摘要 内网穿透是一种方便的技术,可以让用户随时随地访问内网设备。有两种方式可以使用内网穿透:自己搭建,使用nps/frps软件;购买服务,快速享受内网穿透带来的便利。 nps 内网穿透。参考…...

vue3组件库项目学习笔记(八):Git 使用总结
目前组件库的开发已经接近尾声,因为这次是使用 git 进行协作的开发模式,在团队协作的时候遇到很多的问题,开发过程中发现小伙伴们对于 git 的使用还不是很熟练,这里就简单总结一下常用的 git 的操作,大致有:…...

ISO7320FCQDRQ1数字隔离器LMG1025QDEETQ1半桥GaN驱动器
1、数字隔离器 DGTL ISO 3000VRMS 2CH 8SOIC型号:ISO7320FCQDRQ1批次:新技术:容性耦合类型:通用隔离式电源:无通道数:2输入 - 侧 1/侧 2:2/0通道类型:单向电压 - 隔离:30…...

openmmlab 语义分割算法基础
本文是openmmlab AI实战营的第六次课程的笔记,以下是我比较关注的部分。简要介绍语义分割:如下图,左边原图,右边语义分割图,对每个像数进行分类应用语义分割在个各种场景下都非常重要,特别是在自动驾驶和医…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...