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

16、堆基础知识点和priority_queue的模拟实现

news 来源：原创 2025/8/7 10:45:51

一、priority_queue的使用方法

priority_queue的使用方法看这篇文章

二、堆

1、介绍

堆（Heap）是一种特殊的完全二叉树数据结构，满足以下性质：

堆序性质（Heap Property）：
- 大顶堆（Max-Heap）：每个节点的值 ≥ 其子节点的值。
- 小顶堆（Min-Heap）：每个节点的值 ≤ 其子节点的值。
- 完全二叉树：除最后一层外，其他层节点必须填满，且最后一层节点靠左排列。

2、存储方式

堆的存储方式
堆通常用数组实现，利用完全二叉树的性质：

对于节点 i（从 0 开始）：
- 父节点：(i - 1) / 2
- 左子节点：2i + 1
- 右子节点：2i + 2

3、堆的操作过程

堆的常用操作
- 1. 插入元素（Push）
- 步骤：
  - 将新元素添加到数组末尾。
  - 上浮（Percolate Up）：从该节点向上比较并交换，直到满足堆序性质。
- 时间复杂度：O(log n)
1. 删除堆顶（Pop）
- 步骤：
  - 交换堆顶与末尾元素，删除末尾。
  - 下沉（Percolate Down）：从新堆顶向下比较并交换，直到满足堆序性质。
- 时间复杂度：O(log n)
1. 构建堆（Heapify）
- 从最后一个非叶子节点开始，逐个下沉调整。
- 时间复杂度：O(n)（非直觉的线性时间）

4、使用heap函数[algorithm头文件]

make_heap()
- 构建最大堆
push_heap()
- 先使用push_back插入元素到末尾
- 再使用push_heap排序
pop_heap()
- 先使用pop_heap把堆顶放到最后
- 再用pop_back()删除最后一个元素

#include <algorithm>
#include <vector>vector<int> v = {3, 1, 4, 1, 5};// 构建大顶堆
make_heap(v.begin(), v.end()); // [5, 3, 4, 1, 1]// 插入元素
v.push_back(6);
push_heap(v.begin(), v.end()); // [6, 3, 5, 1, 1, 4]// 删除堆顶
pop_heap(v.begin(), v.end()); // 将堆顶移到末尾
v.pop_back(); // [5, 3, 4, 1, 1]

三、实现过程

1、构造

默认vector为底层容器

	//默认构造函数priority_queue(){}

自定义容器

    //构造函数priority_queue(const container& c):data(c){make_heap(data.begin(),data.end());}//可以指定容器

2、插入

在堆的最后插入新元素
插入完毕后，重新排序

    //插入void push(const T& value){data.push_back(value);push_heap(data.begin(),data.end());}

3、删除

删除要先交换堆顶和堆最后一个元素
再进行删除最后一个元素
最后再次排序

    //删除void pop(){if(!empty()){pop_heap(data.begin(),data.end());data.pop_back();}else{throw runtime_error("Priority queue is empty.");}}

4、查看

访问的堆顶值

    T& top(){if(!empty()){return data.front();}}

5、是否为空

为空就是true
否则为false

    bool empty() const{return data.empty();}

6、大小

返回的数据的个数

    size_t size()const{return data.size();}

7、完整过程（大顶堆）


template<class T,class container = vector<T>>
class priority_queue{
private:container data;
public://默认构造函数priority_queue(){}//构造函数priority_queue(const container& c):data(c){make_heap(data.begin(),data.end());}//可以指定容器//插入void push(const T& value){data.push_back(value);push_heap(data.begin(),data.end());}//删除void pop(){if(!empty()){pop_heap(data.begin(),data.end());data.pop_back();}else{throw runtime_error("Priority queue is empty.");}}//访问T& top(){if(!empty()){return data.front();}}bool empty() const{return data.empty();}size_t size()const{return data.size();}
};
int main(){// 使用默认底层容器vectorpriority_queue<int>q1;q1.push(3);q1.push(1);q1.push(4);q1.push(5);cout<<"Top element of q1: "<<q1.top()<<endl;q1.pop();cout << "Priority queue q1 size after pop: " << q1.size() <<endl;//自定义vectorvector<int>v = {9, 5, 7, 2, 6};priority_queue<int,vector<int>>q2(v);cout<<"Top element of q2: "<<q2.top()<<endl;q2.pop();cout<<"Priority queue q2 size after pop: "<<q2.size()<<endl;
}

8、小顶堆

如果要完成小顶堆，就需要逆序排列，可以使用less<typename>的方法来实现。
- 在template里加入less
- 在push_heap等等里面，就可以使用less了。

template<class T,class container = vector<T>,class compare = less<T>>//小顶堆
class priority_queue{
private:container data;
public:void push(const T& value) {data.push_back(value);push_heap(data.begin(), data.end(), compare());}
};

16、堆基础知识点和priority_queue的模拟实现

一、priority_queue的使用方法 priority_queue的使用方法看这篇文章二、堆 1、介绍堆（Heap）是一种特殊的完全二叉树数据结构，满足以下性质： 堆序性质（Heap Property）： 大顶堆&#xff08…...

编程日记 2025/8/7 10:45:51

20250419将405的机芯由4LANE的LVDS OUT配置为8LANE的步骤

20250419将405的机芯由4LANE的LVDS OUT配置为8LANE的步骤 2025/4/19 15:38 查询格式YUV/RGB 81 09 04 24 60 FF 90 50 00 00 FF 查询辨率帧率 81 09 04 24 72 FF 90 50 01 03 FF 查询LVDS mode : Singel output/Dual output 81 09 04 24 74 FF 90 50 00 00 FF 配置405的机…...

编程日记 2025/7/30 12:26:02

【信息系统项目管理师】高分论文：论信息系统项目的采购管理（信息化办公系统）

更多内容请见：备考信息系统项目管理师-专栏介绍和目录文章目录论文1、规划采购管理2、实施采购3、管理采购论文随着信息化技术的发展，从企业到政府，传统的办公模式正在悄然消失，信息化办公模式正成为主流。特别是国务院印发的《关于加快推广“互联网+政务服务”工作的…...

编程日记 2025/8/7 10:40:18

国产GPU生态现状评估：从寒武纪到壁仞的编程适配挑战

近年来，国产GPU厂商在硬件性能上持续突破，但软件生态的构建仍面临严峻挑战。本文以寒武纪、壁仞等代表性企业为例，对比分析其与CUDA生态的兼容性差异，并探讨技术突围路径。一、编程适配的核心挑战 ‌编程模型差异与开发成本‌ …...

编程日记 2025/8/7 10:40:32

Linux（autoDL云服务器）mamba-ssm环境安装——一次成功！

1.创建环境选择torch2.0， cuda11.8，python3.8 2.从GitHub官网下载cp38对应的，causl_conv1d，和mamba-ssm2.2.2。下载入下图所示。 3.直接用finalshell 或者xshell连接服务器上传，到根目录下面。直接用pip install *…...

编程日记 2025/8/7 8:21:02

手搓LeNet-5（基础模型）实现交通标志识别

手搓LeNet-5（基础模型）实现交通标志识别一、环境准备1. 安装Python环境2. 安装CUDA（可选，仅需GPU加速时）3. 配置虚拟环境4. 安装PyTorch核心库5. 安装辅助库6. 验证安装7. 准备数据集8.常见问题处理二、数据集处理三…...

编程日记 2025/8/7 10:40:30

TV主板的拆解学习

下面是小米的电视机主板，电源采用PFCLLC方案，主控采用电视盒子主控采用晶晨半导体T962-H，搭配2G南亚DDR3L内存和8G三星eMMC存储器。本文用来加深对TV主板的认识，学习于充电头网，链接在文末。两颗蓝色插件Y电容来自S…...

编程日记 2025/8/7 10:35:45

PH热榜 | 2025-04-19

1. Omakase.ai Voice 标语：你的语音驱动销售助手。一个链接。介绍：Omakase.ai Voice将您的网站转变为一个语音驱动的销售助手，它可以在客户浏览时进行对话、倾听并给出推荐。聊天机器人往往效果不佳——它们无法实现销售，而这个…...

编程日记 2025/7/30 12:25:51

LeetCode（Hot.2）—— 49.字符异位词分组题解

Problem: 49. 字母异位词分组字母异位词的定义是：两个单词的字母组成一样，但顺序可以不同，比如 eat、tea 和 ate 就是一个组的。思路将每个字符串按字母排序，把排序后的字符串作为 key，相同 key 的放在一个 list 中…...

编程日记 2025/8/5 5:24:16

UE学习记录part19

231 insect: insect enemy type 创建dead动画资源往insect head上添加socket 创建攻击root motion动画。motion warping需要与root motion合作使用为buff_blue创建物理资产设置simulate physic使sinsect死亡后能落到地板上而不是漂浮在空中，要将die函数设置为 -…...

编程日记 2025/8/6 9:46:44

不连续数据区间天数累计sql

计算不连续数据区间天数并且剔除重复天数 create table loan_data(loan_no varchar(10),cust_no varchar(10),start_date date,end_date date )INSERT INTO loan_data VALUES (LN001, CUST001, 2025-01-04, 2025-01-08); INSERT INTO loan_data VALUES (LN002, CUST001, 2025-…...

编程日记 2025/8/7 5:18:21

django基于爬虫的网络新闻分析系统的设计与实现(源码+lw+部署文档+讲解)，源码可白嫖!

摘要本网络新闻分析系统采用B/S架构，数据库是MySQL，网站的搭建与开发采用了先进的Python进行编写，使用了Django框架。该系统从两个对象：由管理员和用户来对系统进行设计构建。前台主要功能包括：用户注册、登录、浏览…...

编程日记 2025/8/6 18:14:30

JAVA文件I/O

目录一、三种路径的分类： 1、绝对路径： 2、相对路径： 3、基准目录： 二、文件的种类： 三、利用JAVA操作文件： 1、File类的构造方法： 2、File 类方法的使用： 使用例子&#…...

编程日记 2025/8/6 14:55:08

第七周作业

一、分别在前端和后端使用联合注入实现“库名-表名-字段名-数据”的注入过程，写清楚注入步骤 1、爆库后端sql语句：select database(); 前端：1 order by 1#，1 order by 2#，1 order by 3# 判断显示位为两位1 union sel…...

编程日记 2025/7/30 12:25:40

Linux 进程信号详解

进程信号信号是进程之间事件异步通知的一种方式，属于软中断。 kill -l //查看不同信号代表的事件执行kill -l 可以看到共有62种信号，其中： 0-31号信号为非可靠信号（这部分信号借鉴于UNIX系统的信号）；…...

编程日记 2025/8/6 5:19:19

MCP 应用案例-网络设备批量管理

案例背景需求痛点企业需管理数百台跨地域网络设备（交换机/路由器），传统方式存在： 人工SSH登录效率低脚本维护成本高（不同厂商CLI语法差异）状态监控依赖独立监控系统解决方案通过MCP协议构建智能网络…...

编程日记 2025/8/6 6:25:20

进程程序替换

fork() 之后,⽗⼦各⾃执⾏⽗进程代码的⼀部分如果⼦进程就想执⾏⼀个全新的程序呢？进程的程序替换来完成这个功能！ 程序替换是通过特定的接⼝，加载磁盘上的⼀个全新的程序(代码和数据)，加载到调⽤进程的地址空间中&#xff01…...

编程日记 2025/8/6 18:28:22

6.7 ChatGPT自动生成定时任务脚本：Python与Cron双方案实战指南

ChatGPT自动生成定时任务脚本：Python与Cron双方案实战指南关键词：定时任务调度, ChatGPT 代码生成, Cron 脚本开发, Python 调度器, 自动化更新系统 6.3 使用 ChatGPT 生成 Cron 调度脚本在 GitHub Sentinel 的定期更新功能中，定时任务调度是核心模块。本节演示如何通过…...

编程日记 2025/8/1 4:53:22

废物九重境弱者学JS第十四天--构造函数以及常用的方法

目录 JavaScript 进阶 - 第2天深入对象构造函数实例成员静态成员内置构造函数 Object Array 包装类型 String Number 案例 JavaScript 进阶 - 第2天了解面向对象编程的基础概念及构造函数的作用，体会 JavaScript 一切皆对象的语言特征&#xff0c…...

编程日记 2025/8/5 19:10:47

机器学习+深度学习

文章目录一、机器学习（一）机器学习概念（二）机器学习基本流程（三）机器学习应用场景二、机器学习的常见工具与相关库（一）Python 机器学习库（二）数据处理库（三）可视化库三、聚类算法思想与模型搭建过程（一）K - Means 聚类算法（二）DBSCAN 聚类算法四、分类算法思想…...

编程日记 2025/7/29 18:59:16

docker基本使用命令

一、镜像 1、拉取镜像 docker pull busybox docker pull nginx:1.26-alpine 2、查看本地镜像 [rootRocky-1 ~]# docker images REPOSITORY TAG IMAGE ID CREATED SIZE nginx latest 4e1b6bae1e48 18 hours ago 192MB busybox lates…...

编程日记 2025/8/2 18:58:12

相机模型--CMOS和CCD的区别

1--CMOS和CCD的工作原理 CCD（Charge Coupled Device，电荷耦合器件）： 1. 图像通过光电效应在感光单元中转化为电荷； 2. 每个像素上的电荷被依次“耦合”并传输到芯片的角落，通过一个或几个模拟输出放大器输…...

编程日记 2025/8/3 4:59:53

触发器（详解）

一：MySQL触发器 MySQL数据库中触发器是一个特殊的存储过程。不同的是执行存储过程要使用 CALL 语句来调用，而触发器的执行不需要使用 CALL 语句来调用，也不需要手工启动，只要一个预定义的事件发生就会被 MySQL自动调用。引发…...

编程日记 2025/8/6 16:42:37

Vue 3 中将 ref 创建的响应式对象数据转换为普通（非响应式）的数据

Vue 3 中使用 ref 创建的响应式对象数据转换为普通（非响应式）的数据，有以下几种方法： 1. 访问 .value 属性: 这是最直接、最常见的方法。由于 ref 对象的值存储在其 .value 属性中，直接访问该属性即可获得普通数据。…...

编程日记 2025/8/4 8:13:15

Vue基础(6)_键盘事件

普通键盘事件键盘事件常用的有两个：keydown、keyup。举例： <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><script type"text/javascript" src"../js/vue.js"&…...

编程日记 2025/8/6 16:09:53

Kubernetes控制平面组件：高可用 APIServer

云原生学习路线导航页（持续更新中） kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计（一）Kubernetes架构原则和对象设计（二）Kubernetes架构原则和对象设计（三）Kubernetes控…...

编程日记 2025/8/3 12:24:27

这个是我的qss按钮样式和之前的// 应用全局样式表 QString style = R“(是会冲突吗，导致我的按钮背景颜色是黑色，我该怎么修改

/* 样式 A */ *[style-type="A"] { background-color:#cfd1d4; border: none; border-radius: 50%; /* 圆形边框 */ padding: 7px 14px; } *[style-type="A"]:hover { background-color: #45a049; }这个是我的qss按钮样式和之前的// 应用全局样式表 QStri…...

编程日记 2025/7/30 12:25:17

Kubernetes控制平面组件：API Server详解（二）

编程日记 2025/7/30 14:05:44

人工智能在智慧农业中的应用：从田间到餐桌的变革

农业是人类社会的基石，随着全球人口的增长和资源的日益紧张，传统农业面临着巨大的挑战。近年来，人工智能（AI）技术的快速发展为农业带来了新的机遇。智慧农业通过将AI技术与农业生产相结合，实现了从田间种植…...

编程日记 2025/7/30 14:05:42

多人3D游戏完整实现方案

以下是一份完整的代码实现方案，涵盖架构设计、核心模块实现和部署流程。我们以多人3D游戏为例，结合之前讨论的Nano服务端框架和Unity客户端：技术栈模块技术选型服务端Golang + Nano框架 + MongoDB客户端Unity 2022 + C# + Mirror Networking通信协议Protobuf + WebSock…...

编程日记 2025/8/6 22:05:21

FFUF指南

ffuf 的核心功能： 目录/文件发现： 通过暴力破解（使用字典）探测目标网站的隐藏目录或文件，例如： ffuf -w /path/to/wordlist.txt -u http://target.com/FUZZ 子域名枚举： 通过模糊测试发现目标…...

编程日记 2025/8/5 14:52:02

详细的PyCharm安装教程

详细的PyCharm安装教程安装前准备确认系统要求： Windows：Microsoft Windows 10 1809 64位或更高版本，Windows Server 2019 64位或更高版本。 macOS：12.0或更高版本。 Linux：满足以下要求的两个最新版本的Ubuntu LTS或…...

编程日记 2025/8/5 4:32:55

FPGA IO引脚 K7-认知4

UG475来知道bank, GTX, Pin数量， Package, Pinout 时钟 SRCC（Single-Region Clock Capable I/O）和MRCC（Multi-Region Clock Capable I/O）是专用的时钟输入/输出引脚。如 2.DQS...

编程日记 2025/7/30 14:05:33

C++——异常

1. C语言错误处理机制我们在曾经介绍过C语言下的错误码。错误码我们过去经常见到，错误码通常是指errno变量中的值，它表示特定操作（如系统调用或库函数）发生错误的原因。errno是一个全局变量，当出现错误时会自动将错误…...

编程日记 2025/8/5 15:16:54

vue3 中 iframe 多页面切换导致资源刷新的问题解决

最近发现一个问题，我在使用 websocket 的时候，在主页面进行了 websocket 连接了之后，再使用 iframe 打开子页面的时候，通常会触发页面刷新，这样就导致 WebSocket 断开，这是因为切换 src 会重新加载 iframe …...

编程日记 2025/7/29 14:16:27

php多种方法实现xss过滤

1. 使用 htmlspecialchars() 函数 htmlspecialchars() 是一个PHP内置函数，用于将特殊字符转换为HTML实体，从而防止浏览器将其解释为HTML或脚本代码。 <?phpfunction sanitizeInput($input) {// 将特殊字符转换为HTML实体return htmlspecialchars($…...

编程日记 2025/8/4 3:44:38

蓝桥杯练习题2

动态规划动态规划三大题型：计数问题、最值问题、存在性问题； 【最小权值】-- 最值问题【题目分析】 import java.util.Arrays; Arrays类中的一个方法：Arrays.fill(int[] m,int n) //给 int 类型(或者char类型/Long类型...)的数组全部空间…...

编程日记 2025/8/6 16:11:31

Python遥感开发之Hurst指数的实现

Python遥感开发之Hurst指数的实现主要讲解Python实现Hurst指数，实现遥感下的Hurst指数，对Hurst指数进行分类，以及结合slope指数实现对未来变化趋势的分析。文章目录 Python遥感开发之Hurst指数的实现0 什么是Hurst指数1 Python实现Hurst指…...

编程日记 2025/8/6 12:38:09

opencv 给图片和视频添加水印

给图片和视频添加水印 1 给图片添加水印2 给视频添加水印 1 给图片添加水印代码如下： 添加水印 imgcv2.imread(r../15day4.10/src/xiaoren.png) img2cv2.imread(r../15day4.10/src/bg.png) h,w,cimg.shapeRIO_img2img2[100:100h,200:200w]img3cv2.cvtColor(img,…...

编程日记 2025/8/2 19:20:08

国网B接口协议图像数据上报通知接口流程详解以及上报失败原因（电网B接口）

文章目录一、B接口协议图像数据上报通知接口介绍B.13.1 接口描述B.13.2 接口流程B.13.3 接口参数B.13.3.1 SIP头字段B.13.3.2 SIP响应码B.13.3.3 XML Schema参数定义 B.13.4 消息示例B.13.4.1 图像数据上报请求B.13.4.2 图像数据上报响应二、B接口图像数据上报通知失败常见问…...

编程日记 2025/8/5 23:24:23

Redis(持久化)

目录一 Redis持久化的方式 1. RDB(Redis Database) 2. AOF(Append Only File) 二对比RDB/AOF 为什么要持久化 Redis是跑在内存上的，但内存上的数据是临时的，Redis服务挂了，数据也就丢失了，所以为了解决上述问题，R…...

编程日记 2025/8/6 18:00:16

Linux系统中的网络管理

1.RHEL9版本中，使用nm进行网络配置，ifcfg不再是网络配置文件的主存储，样式仍然可用，但它不再是NetworkManger存储新网络配置文件的默认位置，RHEL以key-file格式在etc/NetworkManger/system-connections/中存储新的网络…...

编程日记 2025/8/2 16:12:32

【深度学习—李宏毅教程笔记】Transformer

目录一、序列到序列（Seq2Seq）模型 1、Seq2Seq基本原理 2、Seq2Seq模型的应用 3、Seq2Seq模型还能做什么？ 二、Encoder 三、Decoder 1、Decoder 的输入与输出 2、Decoder 的结构 3、Non-autoregressive Decoder 四、Encoder 和 De…...

编程日记 2025/8/2 19:35:14

关于UE5的抗锯齿和TAA

关于闪烁和不稳定现象的详细解释当您关闭抗锯齿技术时，场景中会出现严重的闪烁和不稳定现象，尤其在有细节纹理和小物体的场景中。这种现象的技术原因如下： 像素采样问题在3D渲染中，每个像素只能表示一个颜色值，但…...

编程日记 2025/8/6 16:11:31

交换网络基础

学习目标掌握交换机的基本工作原理掌握交换机的基本配置交换机的基本工作原理交换机是局域网（LAN）中实现数据高效转发的核心设备，工作在数据链路层（OSI 模型第二层），其基本工作原理可概括为 “学习…...

编程日记 2025/7/30 14:05:13

AUTOSAR图解==＞AUTOSAR_SWS_EFXLibrary

AUTOSAR 扩展定点数学函数库(EFX)分析 1. 概述 AUTOSAR (AUTomotive Open System ARchitecture) 是汽车电子控制单元(ECU)软件架构的开放标准。在AUTOSAR架构中，扩展定点数学函数库(Extended Fixed-point library, EFX)提供了一组优化的定点数学运算函数&#xff…...

编程日记 2025/8/6 10:46:08

六边形棋盘格（Hexagonal Grids）的坐标

1. 二位坐标转六边形棋盘的方式 1-1这是“波动式”的这种就是把【方格子坐标】“左右各错开半个格子”做到的具体来说有如下几种情况具体到庙算平台上，是很巧妙的用一个4位整数，前两位为x、后两位为y来进行表示附上计算距离的代码 def get_hex_di…...

编程日记 2025/8/7 8:20:01

李宏毅NLP-5-RNNTNeural TransducerMoChA

RNN Transducer(RNN-T) 循环神经对齐器（RNA，Recurrent Neural Aligner）对CTC解码器的改进，具体内容如下： “RNA”，全称 “Recurrent Neural Aligner”，引用来自 [Sak, et al., INTERSPEECH’17…...

编程日记 2025/7/31 17:29:19

GPT-SoVITS 使用指南

一、简介 TTS（Text-to-Speech，文本转语音）：是一种将文字转换为自然语音的技术，通过算法生成人类可听的语音输出，广泛应用于语音助手、无障碍服务、导航系统等场景。类似的还有SVC（歌声转换&…...

编程日记 2025/8/7 1:48:05

洛谷的几道题

P1000 超级玛丽游戏 # P1000 超级玛丽游戏 ## 题目背景本题是洛谷的试机题目，可以帮助了解洛谷的使用。建议完成本题目后继续尝试 [P1001](/problem/P1001)、[P1008](/problem/P1008)。另外强烈推荐[新用户必读帖](/discuss/show/241461)。 ## 题目描述 …...

编程日记 2025/8/1 17:39:24