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

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

news 2026/2/10 13:35:12

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

UE5 学习系列（二）用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

编程新知 2026/2/10 11:02:44

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

编程新知 2026/2/8 4:37:37

进程地址空间（比特课总结）

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

编程新知 2025/11/15 6:48:52

C++：std::is_convertible

C++标志库中提供is_convertible，可以测试一种类型是否可以转换为另一只类型： template <class From, class To> struct is_convertible; 使用举例： #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

编程新知 2025/6/11 15:23:57

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

编程新知 2026/2/9 21:57:29

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

编程新知 2026/1/23 12:37:51

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

编程新知 2025/8/19 2:57:37

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

编程新知 2026/2/4 20:47:44

多种风格导航菜单 HTML 实现（附源码）

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

编程新知 2026/2/2 2:49:11

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

编程新知 2026/2/4 18:07:02