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

二叉树中堆的实现

news 来源：原创 2025/8/18 14:43:43

1 堆的声明和定义

typedef int HPDateType;
typedef struct Heap {HPDateType* arr;int size;int capcity;
}HP;

与顺序表相似，我们需要一个数组，有效空间大小，有效元素个数

2 堆的初始化

void HPInit(HP*php)
{assert(php);php->arr = NULL;php->size = php->capcity = 0;
}

把数组置空，有效元素个数和有效空间大小置为0

3 堆的销毁

void HPDestroy(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->capcity = php->size = 0;
}

传递的参数当然不能为空，用assert断言，接着把arr的空间释放掉，让size,capcity为0

4 入堆

这里我们需要先讲解思路

首先，堆是用数组储存起来的，如果直接插到数组最后一位是不合理的

如图所示，可能空间是满的，这里就需要们重新开辟空间

同时，为了保证堆为一个有效堆（保证为大堆或者小堆），我们需要重新调整堆的排序

空间开辟

if (php->size == php->capcity)
{int newcapcity = php->capcity == 0 ? 4 : 2 * php->capcity;HPDateType* tmp = (HPDateType*)realloc(php->arr, newcapcity * sizeof(HPDateType));if (tmp == NULL){perror("realloc fail");exit(1);}php->capcity = newcapcity;php->arr = tmp;
}

利用realloc开辟，最后给capcity和arr赋值

堆调整--向上调整--小堆

void AdjustUp(HPDateType* arr, int child)//向上调整
{while (child > 0){int parent = (child - 1) / 2;// <: 小堆// >: 大堆if (arr[child] < arr[parent]){swap(&arr[child], &arr[parent]);//swap函数的形参是两个指针，需要传地址child = parent;parent = (child - 1) / 2;}else {break;}}
}

调整原理：将该入堆元素（child）插到末尾，顺着其父母结点(parent)往上调整，在堆为小堆的条件下，如果该元素比他的父母结点小就交换二者，再让其父母结点成为新的孩子结点，循环往复，直到新的孩子结点跳出，或者直白点说就是下标<0就跳出循环

注意，因为当child走到根结点时也需要比较之后判断是否要交换，所以不能只是parent走到空，必须要child走到空

完整入堆操作的实现

void HPPush(HP* php, HPDateType x)
{assert(php);//判断空间是否足够	if (php->size == php->capcity){int newcapcity = php->capcity == 0 ? 4 : 2 * php->capcity;HPDateType* tmp = (HPDateType*)realloc(php->arr, newcapcity * sizeof(HPDateType));if (tmp == NULL){perror("realloc fail");exit(1);}php->capcity = newcapcity;php->arr = tmp;}php->arr[php->size] = x;AdjustUp(php->arr, php->size);//向上调整++php->size;
}

如果是大堆的调整就把向上调整的" < "改为" > "

最后还需要让最大元素个数+1

5 出堆

思路讲解：这里出堆出的通常是堆顶元素，如果要出堆尾元素只需要让size--即可，意义不大，如果是出堆顶元素，那么这里我们一定不能用顺序表的向前覆盖来写，这样会让整个堆的结构混乱，我们不妨另辟蹊径，继续沿用交换操作，让根结点和最后一个结点交换，再出堆尾让size--，这时候我们关注交换到堆顶的元素，利用向下调整算法，让其成为有效堆

堆调整--向下调整--大堆

void AdjustDown(HPDateType*arr,int parent,int n)
{int child = parent * 2 + 1;while (child<n){// 大堆:<// 小堆:>if (child+1<n&&arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);parent = child;child=parent * 2 + 1;}else {break;}}}

调整原理：从堆顶开始，此时的堆顶设为初始parent，我们取child结点中较大的一个作为比较对象，如过child>parent就交换，再让child成为新的parent，直到调整完成跳出循环，或者child走到最后一个结点

这里我们还需要注意child+1在调整的时候是否越界，以防出现非法访问

完整出堆操作的实现

void HPPop(HP* php) 
{assert(!HPEmpty(php));swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;AdjustDown(php->arr, 0, php->size);
}

其中判空函数

bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

6 借助数据结构堆来实现的堆排序

先来写取堆顶元素的实现

HPDateType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

void HeapSort01(int* arr, int n)
{HP hp;HPInit(&hp);for (int i = 0; i < n; i++){HPPush(&hp,arr[i]);}int i = 0;while (!HPEmpty(&hp)){int top = HPTop(&hp);arr[i++] = top;HPPop(&hp);//删除之后会重新排列}HPDestroy(&hp);
}

这种堆排序借助了入堆和出堆时的堆调整，因为每次出堆我们都获取了堆中最小或者最大的元素，所以最终得到了一个有序序列

7 常规堆排序

思路讲解：首先利用向下堆调整让待排序的数组建堆，接着将堆顶元素和最后一个元素交换，接着再进行堆调整直到end<0，实质上还是堆顶元素一定为最大（小）的出堆操作的运用

有如下示例帮助理解

这里我们实现了把最大元素一个个放到末尾，最终实现堆排序

void HeapSort(int* arr,int n)
{//向下调整建堆for (int i = (n - 2) / 2; i>=0;i--){AdjustDown(arr, i, n);//i是最后一个节点的parent节点}int end = n - 1;while (end>0){swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

完

二叉树中堆的实现

1 堆的声明和定义 typedef int HPDateType; typedef struct Heap {HPDateType* arr;int size;int capcity; }HP; 与顺序表相似，我们需要一个数组，有效空间大小，有效元素个数 2 堆的初始化 void HPInit(HP*php) {assert(php);php->arr …...

编程日记 2025/8/18 14:43:43

概率论的基本知识

逆概率还不懂，改天再想想。联合概率联合概率（Joint Probability） 是概率论中的一个重要概念，用于描述多个随机变量同时取某些值的概率。联合概率可以帮助我们理解多个变量之间的关系。...

编程日记 2025/8/18 2:07:27

LVDS（Low Voltage Differential Signaling）电平详解

一、LVDS的定义与核心特性 LVDS（低压差分信号）是一种低功耗、高速、抗干扰的差分信号传输技术，通过一对互补的电压信号（正负端差值）传递数据。其核心特性包括： 电气特性电压摆幅：差分电压约…...

编程日记 2025/8/16 9:46:51

2024年第十五届蓝桥杯软件C/C++大学A组——五子棋对弈

蓝桥杯原题： 题目描述： “在五子棋的对弈中，友谊的小船说翻就翻？ ” 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着 “ 友谊第一，比赛第二…...

编程日记 2025/8/18 9:44:48

OpenRewrite配方之import语句的顺序——org.openrewrite.java.OrderImports

org.openrewrite.java.OrderImports 是 OpenRewrite 工具库中的一个重要规则（Recipe），专为 Java 项目设计，用于自动化调整 import 语句的顺序，使其符合预定义的代码规范。从而提高代码的一致性和可读性。核心功能排序规则：静态导入优先：默认将静态导入（import stati…...

编程日记 2025/8/18 14:37:02

数字电子技术基础（二十八）——TTL门电路的静态功耗和动态功耗

1 静态功耗门电路的工作需要直流电压源的支持，无论在模拟电路还是在数字电路中，只有在外加直流电源的作用下，半导体二极管具有单向导电性，晶体管的放大能力以及开关特性才能体现出来芯片的电源端正负级。芯片的电源端正负极如果…...

编程日记 2025/8/16 9:50:07

RISC-V汇编学习（四）—— RISCV QEMU平台搭建（基于芯来平台）

RISCV汇编学习系列： RISC-V汇编学习（一）—— 基础认识 RISC-V汇编学习（二）—— 汇编语法 RISC-V汇编学习（三）—— RV指令集 RISC-V汇编学习（四）—— RISCV QEMU平台搭建…...

编程日记 2025/8/18 4:27:57

链表的定义、节点结构、基本操作（C++）

1. 链表的基本概念链表是一种动态数据结构，它的元素（节点）在内存中不一定是连续存储的。每个节点通过指针连接到下一个节点，形成一个链式结构。链表分为单向链表、双向链表和循环链表等，这里主要介绍单向链表。 2. …...

编程日记 2025/8/18 8:56:21

deepseek使用记录21——脑图记录

我们有比前人更先进的工具，为何不利用起来呢？ 工作的时候，问问自己，这个问题是理论问题？还是实践问题？如何在系统中劈开一条可实践路径？系统中的缝，系统中的力量（人先进…...

编程日记 2025/8/18 13:22:58

[多线程]基于阻塞队列(Blocking Queue)的生产消费者模型的实现

标题：[多线程]基于阻塞队列(Blocking Queue)的生产消费者模型的实现水墨不写bug 文章目录一、生产者消费者模型特点：二、实现2.1详细解释1. 成员变量2. 构造函数3. Isfull 和 Isempty4. Push 函数5. Pop 函数6. 析构函数7. GetSize 函数三、总结与多线…...

编程日记 2025/8/18 14:38:02

【时时三省】(C语言基础)输入输出的概念

山不在高，有仙则名。水不在深，有龙则灵。 ----CSDN 时时三省有关数据输入输出的概念从前面的程序中可以看到：几乎每一个C程序都包含输入输出。因为要进行运算，就必须给出数据，而运算的结果当然需要输出&#xff0c…...

编程日记 2025/8/15 10:35:03

基于ragflow中deepdoc对pdf文档的rag系统

基于ragflow中deepdoc对pdf文档的rag系统一、安装 conda环境安装到指定的路径 conda create 包名/环境的名字 rag就是包的名字，ragflow就是环境名； 怎样激活环境？–我是在百度飞桨上面跑的 conda activate /home/aistudio/rag/ragflow …...

编程日记 2025/8/16 9:49:53

基于WebRTC技术的EasyRTC嵌入式音视频SDK：多平台兼容与性能优化

在当今数字化、智能化的时代背景下，实时音视频通信技术已成为众多领域不可或缺的关键技术。基于WebRTC技术的EasyRTC嵌入式音视频SDK，凭借其在ARM、Linux、Windows、安卓、iOS等多平台上的兼容性，为开发者提供了强大的工具，推动了…...

编程日记 2025/8/15 14:50:35

Linux驱动开发实战（四）：设备树点RGB灯

Linux驱动开发实战（四）：设备树点RGB灯文章目录 Linux驱动开发实战（四）：设备树点RGB灯前言一、驱动实现1.1 驱动设计思路1.2 关键数据结构1.3 字符设备操作函数1.4 平台驱动探测函数1.5 匹配表和平台驱动结…...

编程日记 2025/8/15 14:34:35

大模型架构记录5-向量数据库

一倒排索引、KNN、PQ 1.1 基础版本 query -> requery 对问题做处理，处理上下文对query 做 refined query 1.2 向量数据库二搜索逻辑 2.1 knn 2.2 近似KNN 先和N个空间的均值比较再和空间内部的所有点比较，计算最近值。优化一： …...

编程日记 2025/8/16 9:46:41

Fail2ban 使用教程 1. 安装 Fail2ban2. 配置 Fail2ban2.1 创建 jail.local 文件2.2 基本配置参数说明2.3 配置具体服务的监控规则2.3.1 SSH 服务2.3.2 Apache 服务 3. 启动和管理 Fail2ban3.1 启动 Fail2ban 服务3.2 设置 Fail2ban 开机自启3.3 检查 Fail2ban 服务状态3.4 重新…...

编程日记 2025/8/16 11:17:44

Django系列教程（8）——函数视图及通用类视图

目录什么是视图(View)及其工作原理接近现实的函数视图更复杂的案例: 视图处理用户提交的数据基于函数的视图和基于类的视图 Django通用类视图 a. ListView b. DetailView c. CreateView d. UpdateView e. FormView f. DeleteView 小结 Django的视图(view)是处理…...

编程日记 2025/8/18 4:44:33

【C#学习笔记04】C语言格式化输出

引言 printf()函数不仅可以将数据输出到控制台，还可以通过格式化字符串灵活地控制输出的格式。printf()函数的使用规则，包括标志说明、字段宽度、转换精度、长度修饰、转换说明、转义字符。 1. printf()函数概述 printf…...

编程日记 2025/8/16 12:38:00

九点标定和十二点标定的区别

九点标定和十二点标定是机器视觉中常用的两种手眼标定方法，用于建立图像坐标系与机械坐标系之间的映射关系。它们的核心区别在于标定点的数量、变换模型和适用场景。以下是详细对比： 1. 九点标定特点标定点数量：9 个点，通常排…...

编程日记 2025/8/16 12:17:09

qt+opengl 播放yuv视频

一、实现效果二、pro文件 Qt widgets opengl 三、主要代码 #include "glwidget.h"GLWidget::GLWidget(QWidget *parent) : QOpenGLWidget(parent) {connect(&m_timer, &QTimer::timeout, this,[&](){this->update();});m_timer.start(1000/33); }v…...

编程日记 2025/8/17 12:07:31

【揭秘测绘艺术】从基础到法律，绘制地球的智慧蓝图

在人类探索与塑造世界的征途中，有一门古老而又现代的科学默默发挥着基石作用——测绘。它不仅仅是地图的绘制，更是对地球空间信息的精准捕捉与智慧应用。今天，让我们一起走进测绘的世界，解码“测绘”与“基础测绘”的内涵&#xf…...

编程日记 2025/8/17 15:39:52

基于DeepSeek×MWORKS 2025a的ROM Builder自动化降阶实战

一、引言当前，工业仿真领域正经历着前所未有的「智能焦虑」——当自动驾驶算法已能理解城市路网，当大模型开始设计蛋白质结构，这个驱动大国重器研发的核心领域，却仍在与千万级方程组成的庞杂模型艰难博弈。传统仿真降阶如同在数…...

编程日记 2025/8/16 11:27:04

NetAssist 5.0.14网络助手基础使用及自动应答使用方案

以下是NetAssist v5.0.14自动应答功能的详细使用步骤： 一、基础准备： 工具下载网址页面：https://www.cmsoft.cn/resource/102.html 下载安装好后，根据需要可以创建多个server，双击程序图标运行即可，下面…...

编程日记 2025/8/18 2:07:29

MySQL中有哪几种锁？

大家好，我是锋哥。今天分享关于【MySQL中有哪几种锁？】面试题。希望对大家有帮助； MySQL中有哪几种锁？ 1000道互联网大厂Java工程师精选面试题-Java资源分享网在MySQL中，锁是用来控制并发访问的机制，确…...

编程日记 2025/8/17 19:52:49

vue2的webpack(vue.config.js) 怎么使用请求转发 devServer.proxy

首先用 express 搭建后端服务器，注意使用中间件解析json格式的请求体，才会获取到 post 参数 app.use(express.json()); app.js const express require(express) const app express() app.use(express.json()); const port 3000app.post(/api/vue2, …...

编程日记 2025/8/18 11:42:55

【开源+代码解读】Search-R1：基于强化学习的检索增强大语言模型框架3小时即可打造个人AI-search

大语言模型（LLMs）在处理复杂推理和实时信息检索时面临两大挑战：知识局限性（无法获取最新外部知识）和检索灵活性不足（传统方法依赖固定检索流程）。现有方法如检索增强生成（RAG）和工具调用（Tool-Use）存在以下问题： RAG：单轮检索导致上下文不足，无法适应多轮交互场景…...

编程日记 2025/8/16 9:53:59

CSS中固定定位

1.如何设置为固定定位? 给元素设置position: fixed 即可实现固定定位. 可以使用left, right, top ,bottom 四个属性调整位置 2.固定定位的参考点在哪里? 参考他的视口视口-->对于PC浏览器来说,视口就是我们看网页的那扇"窗户". 3.固定定位元素的特点 1.脱离文档…...

编程日记 2025/8/15 11:29:58

Kotlin高效实现 Android ViewPager2 顶部导航：动态配置与性能优化指南

高效实现：强调代码的性能优化。Android ViewPager2：明确技术栈。顶部导航：核心功能点。动态配置与性能优化指南：突出动态配置的灵活性和性能优化的重点。在 Android 开发中，使用 ViewPager2 实现高效的顶部导航&…...

编程日记 2025/8/16 12:43:10

MFCday01、模式对话框

对话框类和应用程序类。 MFC中 Combo Box List Box List Control三种列表控件，日期控件Date Time Picker...

编程日记 2025/8/16 11:46:53

C++ 布尔类型（bool）深度解析

引言在 C 编程里，布尔类型（bool）是一种基础且极为关键的数据类型。它专门用于表达逻辑值，在程序的条件判断、循环控制等诸多方面都发挥着重要作用。接下来，我们将对 C 中的布尔类型展开全面且深入的探讨。一、布尔…...

编程日记 2025/8/16 13:00:54

新鲜速递：OpenAI-Agents-Python：构建智能代理系统的轻量级框架

图片来自于官方README.md 一、什么是OpenAI Agents SDK？ OpenAI Agents SDK是一个轻量级但功能强大的框架，专为构建多智能体工作流而设计。作为OpenAI之前实验项目Swarm的生产级升级版本，该SDK提供了极少但高效的抽象概念，使开发…...

编程日记 2025/8/16 12:51:23

单例模式的五种实现方式

1、饿汉式 ①实现：在类加载的时候就初始化实例 ②优点：线程安全 ③缺点：实例在类加载的时候创建，可能会浪费资源 //饿汉式 public class EagerSingleton{private EagerSingleton(){} //私有构造方法private static EagerSingle…...

编程日记 2025/8/16 6:48:44

行为模式---状态模式

概念状态模式是一种行为模式，用于在内部状态改变的时候改变其行为。它的核心思想就是允许一个对象在其内部状态改变的时候改变它的行为。状态模式通过将对象的状态封装成独立的类，并将其行为委托给当前的状态对象，从而使得对象行为随着状态…...

编程日记 2025/8/16 11:29:10

统一 Elastic 向量数据库与 LLM 功能，实现智能查询

作者：来自 Elastic Sunile Manjee 利用 LLM 功能进行查询解析，并使用 Elasticsearch 搜索模板，将复杂的用户请求转换为结构化的、基于模式的搜索，从而实现高精度查询结果。想象一下，你在搜索“距离 Belongil Beach 25…...

编程日记 2025/8/17 21:41:42

（Lauterbach调试器学习笔记）一、首次连接TriCore开发板调试

Lauterbach调试器学习笔记文章目录 Lauterbach调试器学习笔记前言一、Lauterbach调试器介绍二、调试步骤三、常用代码四、不常用代码，但是很有意思总结前言第一篇简单记录一下Lauterbach调试器的使用过程，主要是想写第二篇python api。一、Lauterba…...

编程日记 2025/8/15 21:30:56

HTML星球大冒险之路线图

第一章：欢迎来到 HTML 星球！ 1.1 宇宙的基石：HTML 是什么？ 🌍 比喻：HTML 是网页世界的「乐高积木」，用标签搭建一切可见内容🎯 目标：理解 HTML 的作用，掌握…...

编程日记 2025/8/18 5:58:46

网络安全与七层架构

网络安全与七层架构随着互联网技术的迅猛发展，网络安全问题日益凸显。网络安全不仅影响到个人用户的信息安全，更是企业及国家安全的重要组成部分。而七层架构（OSI模型）为网络通信提供了理论支撑，能够有效地帮助我们理…...

编程日记 2025/8/16 9:49:17

2025-03-13 学习记录--C/C++-PTA 练习2-17 生成3的乘方表

合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。💪🏻 一、题目描述 ⭐️ 练习2-17 生成3的乘方表输入一个非负整数n，生成一张3的乘方表，输出3^0~$$3^n$$的值…...

编程日记 2025/8/18 10:31:00

改进YOLOv8系列，AAAI 2025，多尺度特征提取自注意力模块，全局信息聚合，即插即用！分享

**论文：https://arxiv.org/pdf/2404.07846 **代码地址: https://github.com/nagejacob/TBSN/blob/main/network/tbsn.py 改进YOLOv8系列：多尺度特征提取自注意力模块，全局信息聚合，即插即用！分享 🚀论文研究概括🚀加入到网络中的理论研究🚀需要修改的代码1 🍀🍀…...

编程日记 2025/8/18 3:03:09

我又又又又又又更新了纯手工编写C++画图，有注释~

再再再次感谢Ttcofee提的问题本次更新内容： 鼠标图案（切换），版本号获取，输入框复制剪切板提前申明：如果运行不了，请到主页查看RedpandaDevc下载，若还是不行就卸了重装。版本号&…...

编程日记 2025/8/17 22:25:54

Vue源码深度解析：从2.x到3.x的架构演进与核心原理剖析

Vue源码深度解析：从2.x到3.x的架构演进与核心原理剖析一、框架演变：从Vue2到Vue3的跨越 1.1 革命性升级 Vue3的发布标志着前端框架进入新纪元，其核心改进体现在三个方面： 性能飞跃：包体积减少41%，初始…...

编程日记 2025/8/16 9:50:09

评委打分5个评委去掉一个最高分和一个最低分取平均分

一键替换max用min 按shiftF6 public static int getMin(int[]scores){int min scores[0];for (int i 0; i < scores.length; i) {if(scores[i]> min){min scores[i];}}return min;} 这里有和c/c不一样的知识点 c/c调用函数类似于java的方法,但是c/c的函数调用需要声明…...

编程日记 2025/8/16 9:52:07

javabean类(测试类之外的类)

altinsert快捷键生成构造方法和get、set方法或者插件ptg（连接外网搜索插件并且下载）...

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

C++ 邻接矩阵（代码）

C邻接矩阵代码，见下： #include<iostream>using namespace std;#define inf -1 class Graph{ private:int vertices;int **edges;public:Graph(int vertices);~Graph();void addEdge(int u, int v, int w);void printGraph(); };Graph::Graph(int …...

编程日记 2025/8/17 16:57:35

Cookie与Session详解

Cookie简介 Cookie 是浏览器提供的持久化存储数据的一种机制。是指某些网站为了辨别用户身份、进行会话跟踪而储存在用户本地终端上的数据（通常经过加密）。以下是关于 Cookie 的详细介绍： Cookie工作原理当你访问一个网站时，该网…...

编程日记 2025/8/18 13:32:08

OpenBMC：BmcWeb 处理http请求

OpenBMC：BmcWeb 读取http请求头-CSDN博客介绍了，在读取完http头后，将调用Connection::handle处理http请求 1.Connection::handle void handle() {...req = std::make_shared<crow::Request>(parser->release(), reqEc);...req->session = userSession;accept …...

编程日记 2025/8/16 9:46:52