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

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

news 2025/7/6 15:10:23

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

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

编程新知 2025/6/23 4:26:10

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

编程新知 2025/6/15 20:37:19

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

编程新知 2025/7/4 2:16:32

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

编程新知 2025/7/4 17:59:29

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

编程新知 2025/6/20 19:09:22

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具，自己手写的难度，恐怕高级程序员花费一年的事件，也…...

编程新知 2025/6/15 11:32:55

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

编程新知 2025/7/6 14:56:09

Python爬虫（二）：爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

编程新知 2025/6/16 20:22:52

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

编程新知 2025/7/4 18:44:11

让回归模型不再被异常值“带跑偏“，MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

编程新知 2025/7/6 11:43:54