数据结构(Java实现)-优先级队列(堆)
队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队
列在这种情况下,数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。
这种数据结构就是优先级队列(Priority Queue)。时,可能需要优先级高的元素先出队列,该中场景下,使用队列显然不合适。
PriorityQueue底层使用了堆这种数据结构,而堆实际就是在完全二叉树的基础上进行了一些调整。
堆的概念
堆总是一棵完全二叉树。
堆中某个节点的值总是不大于或不小于其父节点的值;
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
****
堆的存储方式
可以层序的规则采用顺序的方式来高效存储
对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节点,就会导致空间利用率比较低。
假设i为节点在数组中的下标,
如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子
堆的创建
向下调整建堆


画图可以辅助理解



建堆的时间复杂度
满二叉树也是完全二叉树,此处为了简化使用满二叉树
向下调整 建堆的时间复杂度为O(N)。
堆的插入与删除
堆的插入
堆的插入总共需要两个步骤:
先将元素放入到底层空间中(注意:空间不够时需要扩容)
将最后新插入的节点向上调整,直到满足堆的性质




堆的删除
注意:堆的删除一定删除的是堆顶元素。具体如下:
- 将堆顶元素和堆中最后一个元素交换
- 将堆中有效数据个数减少一个
- 对堆顶元素进行向下调整







PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的
关于PriorityQueue的使用要注意:
使用时必须导入PriorityQueue所在的包
PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常
不能插入null对象,否则会抛出NullPointerException
默认情况下是小堆—即每次获取到的元素都是最小的元素
PriorityQueue常用接口





修改默认的小根堆为大根堆,这里我们直接实现Comparator接口,然后重写该接口中的compare方法


top-k问题:最大或者最小的前k个数据

上述解法并不是最优解
下面这种解法


堆排序
堆排序即利用堆的思想来进行排序,总共分为两个步骤:
- 建堆
升序:建大堆
降序:建小堆 - 利用堆删除思想来进行排序



相关文章:
数据结构(Java实现)-优先级队列(堆)
队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队 列在这种情况下,数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。 这种数据结构就…...
算法通关村第8关【黄金】| 寻找祖先问题
思路:递归三部曲 第一步:确定参数和返回值 题目要求找到指定的结点,就需要返回结点。 题目又涉及到p,q就需要传入p,q,需要遍历传入root 第二步:确定终止条件 当遍历到结点为空说明到底没找到返回空 或者遍历到p,…...
栈和队列(详解)
一、栈 1.1、栈的基本概念 1.1.1、栈的定义 栈(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。 栈顶(Top):线性表允许…...
iOS开发Swift-3-UI与按钮Button-摇骰子App
1.创建新项目Dice 2.图标 删去AppIcon,将解压后的AppIcon.appiconset文件拖入Assets包。 3.将素材点数1-6通过网页制作成2x,3x版本并拖入Asset。 4.设置对应的UI。 5.拖入Button组件并设置style。 6.Ctrl加拖拽将Button拖拽到ViewController里࿰…...
1、[春秋云镜]CVE-2022-32991
文章目录 一、相关信息二、解题思路(手注)三、通关思路(sqlmap) 一、相关信息 靶场提示:该CMS的welcome.php中存在SQL注入攻击。 NVD关于漏洞的描述: 注入点不仅在eid处!!ÿ…...
pdf如何删除其中一页?了解一下这几种删除方法
pdf如何删除其中一页?随着电子文档的广泛应用,PDF已成为最常见的文档格式之一。然而,有时候你可能会发现,你的PDF文档中包含了一些多余的页面,或者你需要删除其中的某一页。那么,该如何删除PDF中的页面呢&a…...
PO设计模式是selenium自动化测试中最佳的设计模式之一
Page Object Model:PO设计模式是selenium自动化测试中最佳的设计模式之一,主要体现在对界面交互细节的封装,也就是在实际测试中只关注业务流程就OK了传统的设计中,在新增测试用例之后,代码会有以下几个问题:…...
yolov8使用C++推理的流程及注意事项
1.下载yolov8项目源码GitHub - ultralytics/ultralytics: NEW - YOLOv8 🚀 in PyTorch > ONNX > OpenVINO > CoreML > TFLite 2.下载opencvReleases - OpenCV,建议版本>4.7.0,选择下载源码, windows版本由于使用的编译器与我们所使用的m…...
深度思考计算机网络面经之二
HTTP2和1.1的区别 HTTP 2.0 和 HTTP 1.1 相比有哪些优势呢? HTTP1.1的队头阻塞问题 服务器必须按照请求接收的顺序来响应,为什么 是因为传统的1.1中没有特定字段来区分一个请求属于哪个,只能按照请求的物理顺序返回, HTTP2解…...
老年人跌倒智能识别算法 opencv
老年人跌倒智能识别算法通过opencvpython深度学习算法框架模型,老年人跌倒智能识别算法能够及时发现老年人跌倒情况,提供快速的援助和救援措施,保障老年人的安全。Python是一种由Guido van Rossum开发的通用编程语言,它很快就变得…...
ros2官方文档(基于humble版本)学习笔记
ros2官方文档(基于humble版本)学习笔记(一) 一、安装ROS2二、按教程学习1.CLI 工具配置环境 由于市面上专门讲ROS2开发的书籍不多,近期看完了《ROS机器人开发实践》其中大部分内容还是基于ROS1写的,涉及top…...
可拖动表格
支持行拖动,列拖动 插件:sortablejs UI: elementUI <template><div><hr style"margin: 30px 0;"><div><!-- 数据里面要有主键id, 否则拖拽异常 --><h2 style"margin-bottom: 30px&qu…...
C++语法基础
这里写目录标题 基础语法第一个程序变量常量的定义关键字标识符命名 (变量命名)sizeof的使用实型(浮点型)字符型转义字符字符串的定义 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 基础语法 第一个程序 …...
Windi CSS和Tailwind CSS以及UnoCSS
最近合作在写一个vue3ts的项目,看到其他人用了一种写法,我觉得很奇怪,之前没见过,他是这样写的 <div class"news flex-1 h-40px flex"></div>我不理解的是为什么这样写就会让这个div的高度就是40px,好多代码…...
c++ opencv将彩色图像按连通域区分
要将彩色图像按连通域区分,您可以使用 OpenCV 中的 cv::connectedComponents 函数。 下面是一个简单的示例代码,说明如何使用 cv::connectedComponents 函数来检测并标记图像中的连通域: #include <opencv2/opencv.hpp> #include <…...
〖程序员的自我修养 - 认知剖析篇⑩〗- 学习编程的高效率方法
人之所以会觉得迷茫,本质上是欠缺对自己的一个控制力、识别庞杂信息、去伪存真的独立思考与认知能力。 说明:该文属于 程序员的自我修养 专栏,购买任意白宝书体系化专栏可加入易编程社区,早鸟价订阅模式除外。福利:加入社区的小伙伴们,除了可以获取博主所有付费专栏的阅读…...
前端基础1——HTML标记语言
文章目录 一、基本了解二、HTML常用标签2.1 文本格式化标签2.2 列表标签2.3 超链接标签2.4 图片标签2.5 表格标签2.6 表单标签2.6.1 提交表单2.6.2 下拉表单2.6.3 按钮标签 2.7 布局标签 一、基本了解 网页组成(index.html页面): HTML标记语言…...
2.1: Dubbo的基本应用-负载均衡,集群容错,服务降级
负载均衡 官网地址: http://dubbo.apache.org/zh/docs/v2.7/user/examples/loadbalance/ 如果在消费端和服务端都配置了负载均衡策略, 以消费端为准。 这其中比较难理解的就是最少活跃调用数是如何进行统计的? 讲道理, 最少活跃数…...
正则常见问题及解决方案
使用正则处理问题的基本思路。有一些方法比较固定,比如将问题分解成多个小问题,每个小问题见招拆招:某个位置上可能有多个字符的话,就⽤字符组。某个位置上有多个字符串的话,就⽤多选结构。出现的次数不确定的话&#…...
docker发布项目及使用外部文件的情况处理
适用docker环境已搭建好 首先项目打jar包:server-cdzh-2.1.0-SNAPSHOT.jar 创建Dockerfile FROM java:8 ADD server-cdzh-2.1.0-SNAPSHOT.jar cdzh.jar EXPOSE 60156 ENTRYPOINT ["java","-jar","/cdzh.jar"] 在linux服务器新建…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
纯 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、…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
