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

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

news 2026/2/8 12:32:53

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

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

编程新知 2025/12/21 20:15:17

YSYX学习记录（八）

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

编程新知 2026/1/24 14:31:01

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

编程新知 2026/1/31 12:27:36

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

编程新知 2026/1/31 4:37:39

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

编程新知 2025/12/14 17:38:21

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

编程新知 2026/1/25 11:46:42

RSS 2025｜从说明书学习复杂机器人操作任务：NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

编程新知 2026/1/31 5:30:51

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

编程新知 2025/10/17 20:59:57

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分，它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构： use strict;/…...

编程新知 2025/10/31 21:11:39

android13 app的触摸问题定位分析流程

一、知识点 一般来说，触摸问题都是app层面出问题，我们可以在ViewRootImpl.java添加log的方式定位；如果是touchableRegion的计算问题，就会相对比较麻烦了，需要通过adb shell dumpsys input > input.log指令，且通过打印堆栈的方式，逐步定位问题，并找到修改方案。 问题…...

编程新知 2026/1/31 13:18:31