【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 系统展示 系统首页界面图 用户注册界面图 医生界面…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...

算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...
41道Django高频题整理(附答案背诵版)
解释一下 Django 和 Tornado 的关系? Django和Tornado都是Python的web框架,但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架,鼓励快速开发和干净、实用的设计。它遵循MVC设计,并强调代码复用。Django有…...

C#中用于控制自定义特性(Attribute)
我们来详细解释一下 [AttributeUsage(AttributeTargets.Class, AllowMultiple false, Inherited false)] 这个 C# 属性。 在 C# 中,Attribute(特性)是一种用于向程序元素(如类、方法、属性等)添加元数据的机制。Attr…...