【Java数据结构】优先级队列(堆)
一. 优先级队列
1 概念
2. 优先级队列的模拟实现
二、堆的概念
1.堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树。

2 堆的存储方式

注意:对于 非完全二叉树,则不适合使用顺序方式进行存储 ,因为为了能够还原二叉树, 空间中必须要存储空节 点,就会导致空间利用率比较低 。
- 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
- 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
- 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子
3 堆的创建
1 堆向下调整
- parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标记
- 将parent与较小的孩子child比较,如果:
- 否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子
- parent小于较小的孩子child,调整结束树不满足此性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。
public void shiftDown(int parent,int usedSize){int child=parent*2+1;while(child<usedSize){// 如果右孩子存在,找到左右孩子中较大的孩子,用child进行标记if(child+1<usedSize&&elem[child]<elem[child+1]){child++;}if(elem[parent]<elem[child]){int tmp=elem[parent];elem[parent]=elem[child];elem[child]=tmp;}else {break;//如果孩子都比父母小}parent=child;child=2*parent+1;}}
注意:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
2 堆的创建
public void createHeap(){// 找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整for(int parent=(usedSize-1-1)/2;parent>=0;parent--){shiftDown(parent,usedSize);}}
3 建堆的时间复杂度
4 堆的插入与删除
(1) 堆的插入

public boolean isFull(){if(elem.length>usedSize){return false;}else {return true;}
}
public void push(int val){//将结点插在最后,再向上调整建堆if(isFull()){elem= Arrays.copyOf(elem,2*elem.length);}elem[usedSize]=val;shiftUp(usedSize);usedSize++;
}
public void shiftUp(int child) {int parent=(child-1)/2;while(parent>=0){if(elem[parent]<elem[child]){int tmp=elem[parent];elem[parent]=elem[child];elem[child]=tmp;child=parent;parent=(child-1)/2;}else {break;}}
}
向上调整的时间复杂度为O(NlogN)。
(2) 堆的删除
5 用堆模拟实现优先级队列
public boolean isEmpty(){return usedSize==0;}public int poll( ) {if(isEmpty()){return -1;}int val=elem[0];swap(elem,0,usedSize-1);shiftDown(0,usedSize-1);usedSize--;return val;}public void swap(int[] elem,int start,int end){int tmp=elem[start];elem[start]=elem[end];elem[end]=tmp;}
1. 下列关键字序列为堆的是 :()A: 100,60,70,50,32,65 B: 60,70,65,50,32,100 C: 65,100,70,32,50,60D: 70,65,100,32,50,60 E: 32,50,100,70,65,60 F: 50,100,70,65,60,322. 已知小根堆为 8,15,10,21,34,16,12 ,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是 ()A: 1 B: 2 C: 3 D: 43. 最小堆 [0,3,2,5,7,4,6,8], 在删除堆顶元素 0 之后,其结果是 ()A: [3 , 2 , 5 , 7 , 4 , 6 , 8] B: [2 , 3 , 5 , 7 , 4 , 6 , 8]C: [2 , 3 , 4 , 5 , 7 , 8 , 6] D: [2 , 3 , 4 , 5 , 6 , 7 , 8][ 参考答案 ]1.A 2.C 3.C
三、常用接口介绍
1 PriorityQueue的特性
- 使用时必须导入PriorityQueue所在的包,即: importjava.util.PriorityQueue;
- PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException异常
- 不能插入null对象,否则会抛出NullPointerException
- 没有容量限制,可以插入任意多个元素,其内部可以自动扩容
- 插入和删除元素的时间复杂度为O(logN)
- PriorityQueue底层使用了堆数据结构
- PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
2 PriorityQueue常用接口介绍
1. 优先级队列的构造

static void TestPriorityQueue(){
// 创建一个空的优先级队列,底层默认容量是11PriorityQueue<Integer> q1 = new PriorityQueue<>();
// 创建一个空的优先级队列,底层的容量为initialCapacityPriorityQueue<Integer> q2 = new PriorityQueue<>(100);ArrayList<Integer> list = new ArrayList<>();list.add(4);list.add(3);list.add(2);list.add(1);
// 用ArrayList对象来构造一个优先级队列的对象
// q3中已经包含了三个元素PriorityQueue<Integer> q3 = new PriorityQueue<>(list);System.out.println(q3.size());System.out.println(q3.peek());}
public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
public class Test {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new intCom());priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);System.out.println(priorityQueue.peek());}
}
此时创建出来的就是一个大堆。
2. 插入/删除/获取优先级最高的元素
函数名 | 功能介绍 |
boolean offer(E e) | 插入元素e,插入成功返回true,如果e对象为空,抛出NullPointerException异常,时间复杂度O(logN),注意:空间不够时候会进行扩容 |
E peek() | 获取优先级最高的元素,如果优先级队列为空,返回null |
E poll() | 移除优先级最高的元素并返回,如果优先级队列为空,返回null |
int size() | 获取有效元素的个数 |
void clear() | 清空 |
boolean isEmpty() | 检测优先级队列是否为空,空返回true |
static void TestPriorityQueue2(){int[] arr = {4,1,9,2,8,0,7,3,6,5};
// 一般在创建优先级队列对象时,如果知道元素个数,建议就直接将底层容量给好
// 否则在插入时需要不多的扩容
// 扩容机制:开辟更大的空间,拷贝元素,这样效率会比较低PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);for (int e: arr) {q.offer(e);}System.out.println(q.size()); // 打印优先级队列中有效元素个数System.out.println(q.peek()); // 获取优先级最高的元素
// 从优先级队列中删除两个元素之和,再次获取优先级最高的元素q.poll();q.poll();System.out.println(q.size()); // 打印优先级队列中有效元素个数System.out.println(q.peek()); // 获取优先级最高的元素q.offer(0);System.out.println(q.peek()); // 获取优先级最高的元素
// 将优先级队列中的有效元素删除掉,检测其是否为空q.clear();if(q.isEmpty()){System.out.println("优先级队列已经为空!!!");
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {int oldCapacity = queue.length;
// Double size if small; else grow by 50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));
// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}
优先级队列的扩容说明:
- 如果容量小于64时,是按照oldCapacity的2倍方式扩容的
- 如果容量大于等于64,是按照oldCapacity的1.5倍方式扩容的
- 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容
3 oj练习
方法1:把所有元素都放去堆排序,然后取前K个
class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();//O(NlogN)for(int i:arr){priorityQueue.offer(i);}int[] elem=new int[k];//O(klogN)for(int i=0;i<k;i++){elem[i]=priorityQueue.poll();}return elem;}
}
时间复杂度:O(NlogN+klogN)=O((N+k)logN)
该解法只是PriorityQueue的简单使用,并不是topK最好的做法,那topk该如何实现?下面介绍:
方法2:把前K个元素创建为大根堆,遍历剩下N-K个元素,和堆顶元素相比较,如果比堆顶元素小,就把堆顶元素删除,插入当前元素
class intCom implements Comparator<Integer>{public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}}
class Solution {public int[] smallestK(int[] arr, int k) {int[] elem=new int[k];if(k==0||arr==null){return elem;}PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new intCom());//O(klogk)for(int i=0;i<k;i++){priorityQueue.offer(arr[i]);}//O((N-k)logk)for(int j=k;j<arr.length;j++){int peekval=priorityQueue.peek();if(arr[j]<peekval){priorityQueue.poll();priorityQueue.offer(arr[j]);}}for(int i=0;i<k;i++){elem[i]=priorityQueue.poll();}return elem;}
}
四. 堆的应用
1 PriorityQueue的实现
2 堆排序
public void shiftDown(int parent,int usedSize){int child=parent*2+1;while(child<usedSize){// 如果右孩子存在,找到左右孩子中较大的孩子,用child进行标记if(child+1<usedSize&&elem[child]<elem[child+1]){child++;}if(elem[parent]<elem[child]){int tmp=elem[parent];elem[parent]=elem[child];elem[child]=tmp;}else {break;//如果孩子都比父母小}parent=child;child=2*parent+1;}}
1. 建堆
常见习题:1. 一组记录排序码为 (5 11 7 2 3 17), 则利用堆排序方法建立的初始堆为 ()A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)答案: C
3 Top-k问题
- 前k个最大的元素,则建小堆
- 前k个最小的元素,则建大堆
相关文章:

【Java数据结构】优先级队列(堆)
【本节目标】 1. 掌握堆的概念及实现 2. 掌握 PriorityQueue 的使用 一. 优先级队列 1 概念 前面学过队列,队列是一种先进先出 (FIFO) 的数据结构 ,但有些情况下, 操作的数据可能带有优先级,一般出队 列时,可…...

图书个性化推荐系统|基于springBoot的图书个性化推荐系统设计与实现(附项目源码+论文+数据库)
私信或留言即免费送开题报告和任务书(可指定任意题目) 目录 一、摘要 二、相关技术 三、系统设计 四、数据库设计 五、核心代码 六、论文参考 七、源码获取 一、摘要 本论文主要论述了如何使用JAVA语言开发一个图书个性化推荐系统&…...
通用车牌正则校验
要编写一个正则表达式来包含所有类型的车牌号,我们需要考虑以下几种常见的车牌类型: 1. 普通汽车车牌(蓝牌/黄牌) 规则:1个汉字 1个字母 5个字母或数字示例:京A12345、粤B5678X 2. 新能源车牌…...
使用 SSH 连接 GitLab 的常见问题及解决方案
使用 SSH 连接 GitLab 的常见问题及解决方案 在使用 SSH 连接到 GitLab 服务器时,可能会遇到类似于以下的错误信息: git192.168.xx.xxx: Permission denied (publickey).这个错误通常表示 SSH 无法验证你的公钥,导致无法访问 GitLab 仓库。…...

泛微E9开发 校验日期型字段是否符合要求
校验日期型字段是否符合要求 1、需求分析及展示效果1.1、需求确认1.2、展示效果 2、实现方法3、扩展知识——js日期相关函数 1、需求分析及展示效果 1.1、需求确认 “填报时间”是一个日期型字段,用户提出需求只能选择每个月的第二个周二,选择其他日期…...
ubuntu安装Vim和net-tools和htop
合并安装,快捷方便 sudo apt update sudo apt install net-tools vim htop在Ubuntu中安装Vim可以通过终端使用以下命令完成: sudo apt update sudo apt install vim这两条命令首先更新了本地的包索引,然后安装了Vim文本编辑器。 安装完成后…...
每天10个js面试题(六)
1、js数组方法? Array.push()此方法是在数组的后面添加新加元素,此方法改变了数组的长度Array.pop()此方法在数组后面删除最后一个元素,并返回数组,此方法改变了数组的长度 Array.shift()此方法在数组后面删除第一个元素…...

AIGC技术的学习 系列二
文章目录 前言一、AIGC是什么?1.1. 基本概念1.2机器学习分类二、 语言模型2.1. 基于统计的语言模型。2.2. 基于神经网络的语言模型。2.3. 基于预训练机制的的语言模型/大语言模型三、读入数据3.1. 不得不说的Transformer3.2. 影响力3.3. 根据人类反馈的强化学习3.4. 生成式AI3…...

惊艳!AI模型DIAMOND可模拟《反恐精英》,单张RTX 3090就能运行
最近,研究人员开发了一种名为 DIAMOND(Diffusion for World Modelling)的 AI 模型,它能够在神经网络中模拟著名的电脑游戏《反恐精英:全球攻势》(CS:GO)。 这个模型在一张 Nvidia RTX3090显卡上运行,能够达到每秒10帧…...

中波长线天线耦合的一个方法
围绕窗外墙外牵了10米的室外天线。 短波,fm都是很简单,一个夹子直接夹在拉杆天线上面,效果已经很好。 今天偶尔听到中波前面大约510khz的地方有个摩尔斯码。是成都附近机场的NDB。这个平时要在楼顶或者很空旷的地方才能收到。音量比较小&am…...

Java基础(6)
深拷贝和浅拷贝区别了解吗?什么是引用拷贝?关于深拷贝和浅拷贝区别,我这里先给结论:浅拷贝:浅拷贝会在堆上创建一个新的对象(区别于引用拷贝的一点),不过,如果原对象内部…...

[JAVAEE] 线程安全问题
目录 一. 什么是线程安全 二. 线程安全问题产生的原因 三. 线程安全问题的解决 3.1 解决修改操作不是原子性的问题 > 加锁 a. 什么是锁 b. 没有加锁时 c. 加锁时 d. 死锁 e. 避免死锁 3.2 解决内存可见性的问题 > volatile关键字 (易变的, 善变的) a. 不加…...
k8s 集群给用户生成 kubeconfig 文件
在 k8s 集群的 RBAC 里有用到用户、组的概念,但是它又不直接管理这些资源,而是通过外部身份验证机制(Authentication Mechanisms)来管理和定义的,比如证书进行签名时,将其配置为 Subject: O system:master…...

(八)Proteus仿真STM32单片机GPIO驱动数码管
1,参考上篇,将LED点阵屏更换成数码管如下图 2,修改驱动函数,数组seg[14]前10个是0-9数字的编码,后四个是空格,点,横线,下划线 char seg_decode(char num)//数字解码 {const char se…...
Python进阶知识1
Python函数 定义一个函数 1.什么是函数:函数是可以重复执行的语句块,可以重复调用 2.作用:用于封装语句块, 提高代码的重用性。 函数是面向过程编程的最小单位 def 语句 1.作用:用来定义( 创建)函数 2…...

单片机设计|基于STM32实现具有室内定位功能的智能手环的设计
作者简介:Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验,被多个学校常年聘为校外企业导师,指导学生毕业设计并参与学生毕业答辩指导,…...

计算机网络——运输层(可靠传输、超时重传、选择确认、流量控制和拥塞控制、TCP连接和释放)
TCP可靠传输的实现 我们假定数据传输只在一个方向进行,即A发送数据,B给出确认。这样的好处是使讨论限于两个窗口,即发送方A的发送窗口和接收方B的接收窗口。 以字节为单位滑动窗口 发送方构造窗口 窗口前沿和后沿的移动情况 描述发送窗口的状…...
Web安全实践
前言 安全无小事,成败在细节,网络有风险,灾难弹指间。 安全一般情况下看不见,在你周围漂浮着,显现出来后,往往会刻骨铭心。正因为安全看不见,所以往往不受重视,因为感知到的概率真…...

【算法篇】动态规划类(2)——01背包+完全背包(笔记)
目录 一、理论基础 1. 问题类型 2. 01背包问题 3. 完全背包问题 4. 解题步骤 (1)确定dp数组(dp table)以及下标的含义。 (2)确定递推公式。 (3)dp数组如何初始化。 &#x…...

基于SpringBoot的“社区医院管理服务系统”的设计与实现(源码+数据库+文档+PPT)
基于SpringBoot的“社区医院管理服务系统”的设计与实现(源码数据库文档PPT) 开发语言:Java 数据库:MySQL 技术:SpringBoot 工具:IDEA/Ecilpse、Navicat、Maven 系统展示 系统首页界面图 用户注册界面图 医生界面…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...