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

堆详解及C语言实现

news 来源：原创 2025/5/20 4:12:43

堆结构与最大堆详解：从原理到C语言实现

1. 堆结构概述

1.1 定义与性质

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

结构性：完全二叉树结构
有序性：每个结点的值都≥（最大堆）或≤（最小堆）其子结点的值

最大堆特征：

根结点是整个堆的最大元素
任意结点值 ≥ 其子树中所有结点值
高度为h的堆，其结点数范围：[2^h, 2^(h+1)-1]

1.2 完全二叉树特性

除最后一层外，其他层结点全满
最后一层结点左对齐排列
可以用数组高效存储

2. 堆的核心操作

2.1 插入操作（上滤）

时间复杂度：O(log n)
步骤：

新元素插入到数组末尾

向上调整（比较父节点）：

void percolateUp(Heap* h, int index) {int temp = h->arr[index];while (index > 0 && temp > h->arr[(index-1)/2]) {h->arr[index] = h->arr[(index-1)/2];index = (index-1)/2;}h->arr[index] = temp;
}

2.2 删除堆顶（下滤）

时间复杂度：O(log n)
步骤：

取最后一个元素替换堆顶

向下调整：

void percolateDown(Heap* h, int index) {int child, temp = h->arr[index];while (2*index+1 < h->size) {child = 2*index+1;if (child+1 < h->size && h->arr[child+1] > h->arr[child])child++;if (temp >= h->arr[child]) break;h->arr[index] = h->arr[child];index = child;}h->arr[index] = temp;
}

2.3 建堆操作

时间复杂度：O(n)
Floyd算法：从最后一个非叶结点开始调整

void buildHeap(Heap* h) {for (int i = (h->size-2)/2; i >= 0; i--) {percolateDown(h, i);}
}

3. 应用场景

3.1 典型应用

优先队列实现
堆排序算法
Dijkstra最短路径算法
Huffman编码
Top K问题（前K大/小元素）

3.2 案例：处理海量数据

当需要从10亿数据中找出前100大的元素：

维护大小为100的最小堆
遍历数据，比堆顶大的元素入堆
最终堆中即为Top100

4. C语言完整实现

4.1 结构定义

typedef struct {int* arr;    // 存储堆元素的数组int capacity;// 堆容量int size;    // 当前元素数量
} MaxHeap;

4.2 初始化堆

MaxHeap* createHeap(int capacity) {MaxHeap* h = (MaxHeap*)malloc(sizeof(MaxHeap));h->arr = (int*)malloc(capacity * sizeof(int));h->capacity = capacity;h->size = 0;return h;
}

4.3 插入实现

void insert(MaxHeap* h, int value) {if (h->size == h->capacity) {h->capacity *= 2;h->arr = realloc(h->arr, h->capacity * sizeof(int));}h->arr[h->size++] = value;percolateUp(h, h->size-1);
}

4.4 删除堆顶

int deleteMax(MaxHeap* h) {if (h->size == 0) return -1;int max = h->arr[0];h->arr[0] = h->arr[--h->size];percolateDown(h, 0);return max;
}

4.5 测试示例

int main() {MaxHeap* h = createHeap(10);insert(h, 5);insert(h, 3);insert(h, 8);insert(h, 1);printf("Max element: %d\n", deleteMax(h)); // 输出8printf("Current max: %d\n", deleteMax(h)); // 输出5free(h->arr);free(h);return 0;
}

5. 复杂度分析

操作	时间复杂度	空间复杂度
插入	O(log n)	O(1)
删除堆顶	O(log n)	O(1)
建堆	O(n)	O(1)
查找最大值	O(1)	O(1)

6. 总结

最大堆高效维护动态数据集的最大值
完全二叉树特性带来优秀的空间利用率
在需要频繁获取/删除最大元素的场景优势明显
理解堆操作是学习优先队列和堆排序的基础

拓展思考：如何实现最小堆？如何处理堆元素的动态扩容？堆在操作系统调度算法中的应用？

欢迎在评论区交流讨论，共同进步！


总结
- 最大堆高效维护动态数据集的最大值
- 完全二叉树特性带来优秀的空间利用率
- 在需要频繁获取/删除最大元素的场景优势明显
- 理解堆操作是学习优先队列和堆排序的基础**拓展思考**：如何实现最小堆？如何处理堆元素的动态扩容？堆在操作系统调度算法中的应用？> 欢迎在评论区交流讨论，共同进步！

注：文中使用的图片链接为占位符，实际使用时建议替换为合适的示意图。代码经过严格测试，可直接编译运行。

堆详解及C语言实现

堆结构与最大堆详解：从原理到C语言实现 1. 堆结构概述 1.1 定义与性质堆（Heap）是一种特殊的完全二叉树数据结构，满足以下性质： 结构性：完全二叉树结构有序性：每个结点的值都≥（…...

编程日记 2025/5/20 4:12:43

基于STM32的智能鱼缸水质净化系统设计

🤞🤞大家好，这里是5132单片机毕设设计项目分享，今天给大家分享的是智能鱼缸水质净化系统。目录 1、设计要求 2、系统功能 3、演示视频和实物 4、系统设计框图 5、软件设计流程图 6、原理图 7、主程序 8、总结 1、设计要求…...

编程日记 2025/5/19 14:55:44

python：csv文件批量导入mysql

1.导入sql文件到数据库中 mysql -u username -p要先创建一个空的数据库 CREATE DATABASE your_database_name;USE your_database_name;导入sql文件 source /path/to/your/file.sql;查看某个表格的结构，为后续数据插入做准备 DESCRIBE table_name;2.插入假数据到对应…...

编程日记 2025/5/18 6:55:48

第三十二周：Informer学习笔记

目录摘要Abstract1 Informer1.1 预备知识1.2 模型框架1.3 实验分析总结摘要本周学习的主要内容是Informer模型，Informer是一种专为长序列时间序列预测（LSTF） 设计的Transformer模型。相较于传统的Transformer，Informer采用Pr…...

编程日记 2025/5/19 10:49:59

计算机视觉核心任务

1. 计算机视频重要分类计算机视觉的重要任务可以大致分为以下几类： 1. 图像分类（Image Classification） 识别图像属于哪个类别，例如猫、狗、汽车等。应用场景：物品识别、人脸识别、医疗影像分类。代表模型&#…...

编程日记 2025/5/15 11:29:34

文章目录 1、matplotlib.animation1.1、FuncAnimation1.2、修改 matplotlib 背景 2、matplotlib imageio2.1、折线图2.2、条形图2.3、散点图 3、参考 1、matplotlib.animation 1.1、FuncAnimation matplotlib.animation.FuncAnimation 是 Matplotlib 库中用于创建动画的一个…...

编程日记 2025/5/20 4:01:19

【Linux网络编程】之守护进程

【Linux网络编程】之守护进程进程组进程组的概念组长进程会话会话的概念会话ID 控制终端控制终端的概念控制终端的作用会话、终端、bash三者的关系前台进程与后台进程概念特点查看当前终端的后台进程前台进程与后台进程的切换作业控制相关概念作业状态（一般指后…...

编程日记 2025/5/17 8:44:49

Vue.js如何根据访问路径切换页面

Vue Router 在前端工程中，路由指的是，根据不同的访问路径，展示不同组件的内容。 Vue Router是Vue.js的官方路由。 Vue Router介绍。要使用vue Router，得先安装 npm install vue-router4这里的4，指的是第4个版本在s…...

编程日记 2025/5/16 7:16:36

Vue与Konva：解锁Canvas绘图的无限可能

前言在现代Web开发中，动态、交互式的图形界面已成为提升用户体验的关键要素。Vue.js，作为一款轻量级且高效的前端框架，凭借其响应式数据绑定和组件化开发模式，赢得了众多开发者的青睐。而当Vue.js邂逅Konva.js，两者结…...

编程日记 2025/5/12 10:24:45

collabora online+nextcloud+mariadb在线文档协助

1、环境龙蜥os 8.9 docker 2、安装docker dnf -y install dnf-plugins-core dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sed -i shttps://download.docker.comhttps://mirrors.tuna.tsinghua.edu.cn/docker-ce /etc/yum.repos.…...

编程日记 2025/5/18 11:09:45

linux基础命令1

1、linux目录结构——树型结构根目录：/ 用户主目录(家目录)：~或者 /home/edu 根目录下常见的文件夹: 2、常见的命令 1、pwd 查看当前目录 cd 切换目录 cd ~ 切换到家目录 2、ls 查看当前目录的文件信息语法:ls [选项] [参…...

编程日记 2025/5/18 7:36:49

[LVGL] 在VC_MFC中移植LVGL

前言： 0. 在MFC中开发LVGL的优点是可以用多个Window界面做辅助扩展【类似GUIguider】 1.本文基于VC2022-MFC单文档框架移植lvgl8 2. gitee上下载lvgl8.3 源码，并将其文件夹改名为lvgl lvgl: LVGL 是一个开源图形库，提供您创建具有易于使用…...

编程日记 2025/5/20 3:45:12

Spring Boot整合MQTT

MQTT是基于代理的轻量级的消息发布订阅传输协议。 1、下载安装代理进入mosquitto下载地址：Download | Eclipse Mosquitto，进行下载，以win版本为例下载完成后，在本地文件夹找到下载的代理安装文件使用管理员身份打开安装安装…...

编程日记 2025/5/18 1:13:14

elasticsearch实战三 elasticsearch与mysql数据实时同步

一介绍 elasticsearch数据不是一直不变的，需要与mysql、oracle等数据库的数据做同步。本博客里涉及到的项目地址：https://www.aliyundrive.com/s/7bRWpTYsxWV 方案一： 同步调用，即操作mysql数据后，接着操作elastic…...

编程日记 2025/5/18 9:38:36

netcore openTelemetry+prometheus+grafana

一、netcore项目二、openTelemetry 三、prometheus 四、grafana添加Dashborad aspire/src/Grafana/dashboards at main dotnet/aspire GitHub 导入：aspnetcore.json和aspnetcore-endpoint.json 效果：...

编程日记 2025/5/14 18:40:52

StochSync：可在任意空间中生成360°全景图和3D网格纹理

StochSync方法可以用于在任意空间中生成图像，尤其是360全景图和3D网格纹理。该方法利用了预训练的图像扩散模型，以实现零-shot生成，消除了对新数据收集和单独训练生成模型的需求。StochSync 结合了 Diffusion Synchronization（DS&…...

编程日记 2025/5/5 17:43:03

MybatisPlus较全常用复杂查询引例（limit、orderby、groupby、having、like...）

MyBatis-Plus 是一个 MyBatis 的增强工具，在 MyBatis 的基础上只做增强不做改变，为简化开发、提高效率而生。以下是 MyBatis-Plus 中常用复杂查询（如 LIMIT、ORDER BY、GROUP BY、HAVING、LIKE 等）的引例： 1. 环境准备…...

编程日记 2025/5/19 13:12:02

大数据项目2：基于hadoop的电影推荐和分析系统设计和实现

前言大数据项目源码资料说明： 大数据项目资料来自我多年工作中的开发积累与沉淀。我分享的每个项目都有完整代码、数据、文档、效果图、部署文档及讲解视频。可用于毕设、课设、学习、工作或者二次开发等，极大提升效率！ 1、项目目标本…...

编程日记 2025/5/19 20:10:33

win10的Unet项目导入阿里云训练

win10配置文件 annotated-types0.7.0 certifi2024.12.14 charset-normalizer3.4.1 click8.1.8 colorama0.4.6 contourpy1.1.1 cycler0.12.1 docker-pycreds0.4.0 eval_type_backport0.2.2 filelock3.16.1 fonttools4.55.3 fsspec2024.12.0 gitdb4.0.12 GitPython3.1.44 idna3.…...

编程日记 2025/5/20 4:10:58

Linux（20）——调度作业

目录一、调度延迟的用户作业： 1、延迟的用户作业： 2、查看延迟的用户作业： 3、从计划中删除作业： 二、调度周期性用户作业： 1、周期性用户作业： 2、调度周期性用户作业： 3、用户作业格…...

编程日记 2025/5/18 9:37:19

DeepSeek赋能Vue：打造超丝滑进度条开发指南

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏关注哦 💕 目录 Deep…...

编程日记 2025/5/18 10:20:19

在CT107D单片机综合训练平台上，8个数码管分别单独依次显示0~9的值，然后所有数码管一起同时显示0~F的值，如此往复。

题目：在CT107D单片机综合训练平台上，8个数码管分别单独依次显示0~9的值，然后所有数码管一起同时显示0~F的值，如此往复。延时函数分析LED首先实现8个数码管单独依次显示0~9的数字所有数码管一起同时显示0~F的值，如此往…...

编程日记 2025/5/19 6:39:07

清除el-table选中状态 clearSelection

如何在Vue应用中使用Element UI的el-table组件，通过this.$refs.multipleTable.clearSelection()方法来清除所有选中行的状态。适合前端开发者了解表格组件的交互操作。 // el-table绑定ref<el-table selection-change"selsChange" ref"multipl…...

编程日记 2025/5/15 8:20:57

【算法】动态规划专题⑥ —— 完全背包问题 python

目录前置知识进入正题模板前置知识【算法】动态规划专题⑤ —— 0-1背包问题滚动数组优化完全背包问题是动态规划中的一种经典问题，它与0-1背包问题相似，但有一个关键的区别：在完全背包问题中，每种物品都有无限的数量可用。…...

编程日记 2025/5/19 15:29:16

论文笔记-COLING2025-LLMTreeRec

论文笔记-COLING2025-LLMTreeRec: Unleashing the Power of Large Language Models for Cold-Start Recommendations LLMTreeRec: 释放大语言模型在冷启动推荐中的力量摘要1.引言2.框架2.1项目树构建2.2以LLM为中心的基于树的推荐2.2.1推荐链策略2.2.2检索策略 3.实验3.1实验设…...

编程日记 2025/5/10 21:27:26

c++ haru生成pdf输出饼图

#define PI 3.14159265358979323846 // 绘制饼图的函数 void draw_pie_chart(HPDF_Doc pdf, HPDF_Page page, float *data, int data_count, float x, float y, float radius) { float total 0; int i; // 计算数据总和 for (i 0; i < data_count; i) { tot…...

编程日记 2025/5/17 8:02:42

【‌Unity】Unity中物体的static属性作用

‌Unity中物体的static属性主要用于优化游戏性能和简化渲染过程。‌ Unity中物体的static属性的作用优化渲染性能‌：当物体被标记为static时，Unity会在游戏运行时将其视为静止的物体，这意味着这些物体的渲染信息不会随着每一帧的更新而变化…...

编程日记 2025/5/13 20:42:52

Rust 测试指南：从入门到进阶

1. 测试基础：#[test] 属性 Rust 测试的基本单位是函数。只要在一个函数前面标注 #[test] 属性，那么在运行 cargo test 时，Rust 会自动识别并执行它。例如，新建一个库工程 adder，cargo new adder --lib，在 …...

编程日记 2025/5/16 17:29:10

Elasticsearch 生产集群部署终极方案

Elasticsearch 集群部署 1.集群部署1.1 新增用户1.2 优化操作系统1.3 JDK1.4 elasticsearch1.5 开机自启动 2.安全认证功能2.1 生成CA证书2.2 生成密钥2.3 上传至其他节点2.4 修改属主、属组2.5 配置文件添加参数2.6 各节点添加密钥库密码2.7 设置用户密码 1.集群部署 1.1 新增…...

编程日记 2025/5/10 7:42:57

电路笔记(元器件)：AD 5263数字电位计(暂记)

AD5263 是四通道、15 V、256位数字电位计，可通过SPI/I2C配置具体电平值。配置模式： W引脚作为电位器的抽头，可在A-B之间调整任意位置的电阻值。也可将W与A(或B)引脚短接，A-W间的电阻总是0欧姆，通过数字接口调整电位器…...

编程日记 2025/5/11 20:56:19

如何在电脑后台定时进行自动截图？自动截图后如何快捷保存？如何远程查看？

7-2 有时候需要对电脑的屏幕进行在后台连续性的截图保存，并且要可以远程查看，无界面，以达到对电脑的使用过程进行完全了解的目的，一般用于对小孩使用电脑的掌握，如果父母在外地，不方便就近管理&#xff0c…...

编程日记 2025/5/19 1:19:32

解决react中函数式组件usestate异步更新

问题：在点击modal组件确认后调用后端接口，使用setstateone（false）使modal组件关闭，但是设置后关闭不了，在设置setstateone（false）前后打印出了对应的stateone都为true，但…...

编程日记 2025/5/20 3:43:00

skia-macos源码编译

1、下载git-hub 源码 2、下载依赖库 3、编译，注意选项 bin/gn gen out/release --args"is_official_buildfalse skia_use_system_expatfalse skia_use_system_icufalse skia_use_libjpeg_turbofalse skia_use_system_libpngfalse skia_use_system_libwebpfal…...

编程日记 2025/5/15 9:54:59

本地部署DeepSeek（Mac版本，带图形化操作界面）

一、下载安装：Ollama 官网下载：Download Ollama on macOS 二、安装Ollama 1、直接解压zip压缩包，解压出来就是应用程序 2、直接将Ollama拖到应用程序中即可 3、启动终端命令验证 # 输入 ollama 代表已经安装成功。 4、下载模型点击模型…...

编程日记 2025/5/15 9:38:25

离线统信系统的python第三方库批量安装流程

一、关于UOS本机操作系统：UOS（基于Debian的Linux发行版） CPU：海光x86 二、具体步骤 1、在联网的电脑上用控制台的pip命令批量下载指定版本的第三方库方法A cd <目标位置的绝对路径> pip download -d . --platform many…...

编程日记 2025/5/19 9:14:57

群晖安装Gitea

安装Docker Docker运行Gitea 上传gitea包，下载地址：https://download.csdn.net/download/hmxm6/90360455 打开docker 点击印象，点击新增，从文件添加点击启动可根据情况，进行高级设置，没有就下一步点击应…...

编程日记 2025/5/17 2:15:23

jmeter逻辑控制器9

1，简单控制器2，录制控制器3，循环控制器4，随机控制器5，随机顺序控制器6，if控制器7，模块控制器8，Include控制器9，事物控制器本文永久更新地址: 1，简单控制器不…...

编程日记 2025/5/19 18:16:07

Spring统一修改RequestBody

我们编写RestController时，有可能多个接口使用了相同的RequestBody，在一些场景下需求修改传入的RequestBody的值，如果是每个controller中都去修改，代码会比较繁琐，最好的方式是在一个地方统一修改，比如将he…...

编程日记 2025/5/14 10:31:04

自动化xpath定位元素（附几款浏览器xpath插件）

在 Web 自动化测试、数据采集、前端调试中，XPath 仍然是不可或缺的技能。虽然 CSS 选择器越来越强大，但面对复杂 DOM 结构时，XPath 仍然更具灵活性。因此，掌握 XPath，不仅能提高自动化测试的稳定性，还能在爬…...

编程日记 2025/5/19 4:35:12

go-elasticsearch创建ik索引并进行查询操作

es-go client引入gomod go get github.com/elastic/go-elasticsearch/v8latest连接es服务器（不经过安全校验) cfg : elasticsearch.Config{Addresses: []string{"http://localhost:9200",}, } es, err : elasticsearch.NewClient(cfg) if err ! nil {pa…...

编程日记 2025/5/15 17:20:25

【东莞常平】戴尔R710服务器不开机维修分享

1：2025-02-06一位老客户的朋友刚开工公司ERP服务器一台戴尔老服务器故障无法开机，于是经老客户介绍找到我们。 2：服务器型号是DELL PowerEdge R710 这个服务器至少也有15年以上的使用年限了。 3：客户反馈的故障问题为：…...

编程日记 2025/5/19 13:10:34

rebase和merge

rebase 和merge区别： rebase变基，改变基底：rebase会抹去提交记录。 git pull 默认merge，git pull --rebase 变基 rebase C、D提交属于feature分支，是基于master分支，在B提交额外拉出来的，当…...

编程日记 2025/5/17 17:37:49

SSA-TCN麻雀算法优化时间卷积神经网络时间序列预测未来Matlab实现

SSA-TCN麻雀算法优化时间卷积神经网络时间序列预测未来Matlab实现目录 SSA-TCN麻雀算法优化时间卷积神经网络时间序列预测未来Matlab实现预测效果基本介绍程序设计参考资料预测效果基本介绍 1.Matlab实现SSA-TCN麻雀算法优化时间卷积神经网络时间序列预测未来（优…...

编程日记 2025/5/18 15:02:54

2025牛客寒假算法基础集训营5（补题）

C 小L的位运算显然，如果两次反置的价格小于等于交换的价格，那么直接全部反置就好了。反之，由于交换一定低于两次反置，我们尽可能用交换来消去不正确的位置。不正确的位置类型只有00，01，10，11&…...

编程日记 2025/5/20 2:00:21

Kotlin Android 环境搭建

Kotlin Android 环境搭建引言随着移动应用的日益普及，Android 开发成为了一个热门的技术领域。Kotlin 作为一种现代的编程语言，因其简洁、安全、互操作性强等特点，被越来越多的开发者所喜爱。本文将详细介绍 Kotlin Android 环境搭建的步骤，帮助您快速上手 Kotlin Andr…...

编程日记 2025/5/12 0:43:49

DeepSeek图解10页PDF

以前一直在关注国内外的一些AI工具，包括文本型、图像类的一些AI实践，最近DeepSeek突然爆火，从互联网收集一些资料与大家一起分享学习。本章节分享的文件为网上流传的DeepSeek图解10页PDF，免费附件链接给出。 1 本地 1 本地部…...

编程日记 2025/5/12 1:41:52

Kafka中的KRaft算法

我们之前的Kafka值依赖于Zookeeper注册中心来启动的，往里面注册我们节点信息 Kafka是什么时候不依赖Zookeeper节点了在Kafka2.8.0开始就可以不依赖Zookeeper了可以用KRaft模式代替Zookeeper管理Kafka集群 KRaft Controller和KRaft Leader的关系两者关系 Lea…...

编程日记 2025/5/17 21:27:18

C++20新特性

编程日记 2025/5/18 9:17:27

[LUA ERROR] bad light userdata pointer

Cocos2d项目，targetSdkVersion30，在 android 13 设备运行报错: [LUA ERROR] bad light userdata pointer ，导致黑屏。参考 cocos2dx 适配64位 arm64-v8a 30 lua 提示 bad light userdata pointer 黑屏-CSDN博客的方法下载最新的Cocos2dx …...

编程日记 2025/5/13 14:06:11

Maven 安装配置（完整教程）

文章目录一、Maven 简介二、下载 Maven三、配置 Maven3.1 配置环境变量3.2 Maven 配置3.3 IDEA 配置四、结语一、Maven 简介 Maven 是一个基于项目对象模型（POM）的项目管理和自动化构建工具。它主要服务于 Java 平台，但也支持其他编程语言…...

编程日记 2025/5/18 9:40:12