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

数据结构（Java实现）-优先级队列(堆)

news 2026/2/10 14:49:02

队列是一种先进先出(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)。

堆的插入与删除
堆的插入
堆的插入总共需要两个步骤：
先将元素放入到底层空间中(注意：空间不够时需要扩容)
将最后新插入的节点向上调整，直到满足堆的性质
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

堆的删除
注意：堆的删除一定删除的是堆顶元素。具体如下：

  1. 将堆顶元素和堆中最后一个元素交换
  2. 将堆中有效数据个数减少一个
  3. 对堆顶元素进行向下调整
    4.
    在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

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

PriorityQueue常用接口
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

修改默认的小根堆为大根堆，这里我们直接实现Comparator接口，然后重写该接口中的compare方法
在这里插入图片描述

在这里插入图片描述

top-k问题：最大或者最小的前k个数据
在这里插入图片描述
上述解法并不是最优解
下面这种解法
在这里插入图片描述
在这里插入图片描述

堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  1. 建堆
    升序：建大堆
    降序：建小堆
  2. 利用堆删除思想来进行排序

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

相关文章：

数据结构（Java实现）-优先级队列(堆)

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队 列在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。 这种数据结构就…...

编程日记 2023/8/30 6:05:28

算法通关村第8关【黄金】| 寻找祖先问题

思路：递归三部曲 第一步：确定参数和返回值 题目要求找到指定的结点，就需要返回结点。 题目又涉及到p,q就需要传入p,q，需要遍历传入root 第二步：确定终止条件 当遍历到结点为空说明到底没找到返回空 或者遍历到p,…...

编程日记 2023/8/30 6:04:27

栈和队列（详解）

一、栈 1.1、栈的基本概念 1.1.1、栈的定义 栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。 栈顶（Top）：线性表允许…...

编程日记 2023/8/30 6:03:26

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里&#xff0…...

编程日记 2023/8/30 6:02:25

1、[春秋云镜]CVE-2022-32991

文章目录 一、相关信息二、解题思路（手注）三、通关思路（sqlmap） 一、相关信息 靶场提示：该CMS的welcome.php中存在SQL注入攻击。 NVD关于漏洞的描述： 注入点不仅在eid处！！&#xff…...

编程日记 2023/8/30 6:01:24

pdf如何删除其中一页？了解一下这几种删除方法

pdf如何删除其中一页？随着电子文档的广泛应用，PDF已成为最常见的文档格式之一。然而，有时候你可能会发现，你的PDF文档中包含了一些多余的页面，或者你需要删除其中的某一页。那么，该如何删除PDF中的页面呢&a…...

编程日记 2023/8/30 6:00:23

PO设计模式是selenium自动化测试中最佳的设计模式之一

Page Object Model：PO设计模式是selenium自动化测试中最佳的设计模式之一，主要体现在对界面交互细节的封装，也就是在实际测试中只关注业务流程就OK了传统的设计中，在新增测试用例之后，代码会有以下几个问题&#xff1a…...

编程日记 2023/8/30 5:59:21

yolov8使用C++推理的流程及注意事项

1.下载yolov8项目源码GitHub - ultralytics/ultralytics: NEW - YOLOv8 🚀 in PyTorch > ONNX > OpenVINO > CoreML > TFLite 2.下载opencvReleases - OpenCV,建议版本>4.7.0,选择下载源码， windows版本由于使用的编译器与我们所使用的m…...

编程日记 2023/8/30 5:58:20

深度思考计算机网络面经之二

HTTP2和1.1的区别 HTTP 2.0 和 HTTP 1.1 相比有哪些优势呢？ HTTP1.1的队头阻塞问题 服务器必须按照请求接收的顺序来响应，为什么 是因为传统的1.1中没有特定字段来区分一个请求属于哪个，只能按照请求的物理顺序返回， HTTP2解…...

编程日记 2023/8/30 5:57:19

老年人跌倒智能识别算法 opencv

老年人跌倒智能识别算法通过opencvpython深度学习算法框架模型，老年人跌倒智能识别算法能够及时发现老年人跌倒情况，提供快速的援助和救援措施，保障老年人的安全。Python是一种由Guido van Rossum开发的通用编程语言，它很快就变得…...

编程日记 2023/8/30 5:56:18

ros2官方文档（基于humble版本）学习笔记

ros2官方文档（基于humble版本）学习笔记（一） 一、安装ROS2二、按教程学习1.CLI 工具配置环境 由于市面上专门讲ROS2开发的书籍不多，近期看完了《ROS机器人开发实践》其中大部分内容还是基于ROS1写的，涉及top…...

编程日记 2023/8/30 5:55:17

可拖动表格

支持行拖动&#xff0c;列拖动 插件&#xff1a;sortablejs UI: elementUI <template><div><hr style"margin: 30px 0;"><div><!-- 数据里面要有主键id&#xff0c; 否则拖拽异常 --><h2 style"margin-bottom: 30px&qu…...

编程日记 2023/8/30 5:54:15

C++语法基础

这里写目录标题 基础语法第一个程序变量常量的定义关键字标识符命名 &#xff08;变量命名&#xff09;sizeof的使用实型&#xff08;浮点型&#xff09;字符型转义字符字符串的定义 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 基础语法 第一个程序 …...

编程日记 2023/8/30 5:53:14

Windi CSS和Tailwind CSS以及UnoCSS

最近合作在写一个vue3ts的项目&#xff0c;看到其他人用了一种写法&#xff0c;我觉得很奇怪&#xff0c;之前没见过&#xff0c;他是这样写的 <div class"news flex-1 h-40px flex"></div>我不理解的是为什么这样写就会让这个div的高度就是40px,好多代码…...

编程日记 2023/8/30 5:52:13

c++ opencv将彩色图像按连通域区分

要将彩色图像按连通域区分&#xff0c;您可以使用 OpenCV 中的 cv::connectedComponents 函数。 下面是一个简单的示例代码&#xff0c;说明如何使用 cv::connectedComponents 函数来检测并标记图像中的连通域&#xff1a; #include <opencv2/opencv.hpp> #include <…...

编程日记 2023/8/30 5:51:12

〖程序员的自我修养 - 认知剖析篇⑩〗- 学习编程的高效率方法

人之所以会觉得迷茫，本质上是欠缺对自己的一个控制力、识别庞杂信息、去伪存真的独立思考与认知能力。 说明：该文属于 程序员的自我修养 专栏，购买任意白宝书体系化专栏可加入易编程社区，早鸟价订阅模式除外。福利：加入社区的小伙伴们，除了可以获取博主所有付费专栏的阅读…...

编程日记 2023/8/30 5:50:11

前端基础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 布局标签 一、基本了解 网页组成&#xff08;index.html页面&#xff09;&#xff1a; HTML标记语言…...

编程日记 2023/8/30 5:49:10

2.1: Dubbo的基本应用-负载均衡,集群容错,服务降级

负载均衡 官网地址&#xff1a; http://dubbo.apache.org/zh/docs/v2.7/user/examples/loadbalance/ 如果在消费端和服务端都配置了负载均衡策略&#xff0c; 以消费端为准。 这其中比较难理解的就是最少活跃调用数是如何进行统计的&#xff1f; 讲道理&#xff0c; 最少活跃数…...

编程日记 2023/8/30 5:48:09

正则常见问题及解决方案

使用正则处理问题的基本思路。有一些方法比较固定&#xff0c;比如将问题分解成多个小问题&#xff0c;每个小问题见招拆招&#xff1a;某个位置上可能有多个字符的话&#xff0c;就⽤字符组。某个位置上有多个字符串的话&#xff0c;就⽤多选结构。出现的次数不确定的话&#…...

编程日记 2023/8/30 5:47:07

docker发布项目及使用外部文件的情况处理

适用docker环境已搭建好 首先项目打jar包&#xff1a;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服务器新建…...

编程日记 2023/8/30 5:46:06

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

编程新知 2025/11/28 2:51:33

反向工程与模型迁移：打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

编程新知 2025/9/15 5:56:53

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

编程新知 2025/12/20 12:32:08

从深圳崛起的“机器之眼”：赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

编程新知 2026/2/8 7:23:45

MVC 数据库

MVC 数据库 引言 在软件开发领域，Model-View-Controller（MVC）是一种流行的软件架构模式，它将应用程序分为三个核心组件：模型（Model）、视图（View）和控制器（Controller）。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系，以…...

编程新知 2025/10/30 4:58:11

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

编程新知 2025/10/7 0:32:40

html-＜abbr＞ 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

编程新知 2026/1/24 19:22:03

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

编程新知 2026/2/4 10:28:25

纯 Java 项目（非 SpringBoot）集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 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、…...

编程新知 2025/9/26 12:26:35

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

编程新知 2025/10/22 6:06:44