数据结构《堆》
堆是一种特殊的数据结构它不同与我们队列和栈堆属于二叉树的范畴另外堆分为大堆和小堆大堆简单理解为就是父节点大于等于它的子节点小堆就是父节点小于等于它的子节点大堆小堆都属于完全二叉树。为了便于访问各个节点这里使用数组实现堆。已知父节点是i那么左子树就是2i1柚子树就是2i2已知任意一个子树节点的下标是i那么它的父节点就是i-1/2这是因为整数的除法只保留整数位。一、创建堆的结构体typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap;这里的结构体内容同顺序表一样二、堆的初始化//堆的初始化 void HeapInit(Heap* php) { assert(php); php-_a NULL; php-_capacity 0; php-_size 0; }三、堆的销毁// 堆的销毁 void HeapDestory(Heap* hp) { assert(hp); if (hp-_a NULL) { return; } free(hp-_a); hp-_capacity 0; hp-_size 0; }四、堆的插入//向上调整 void AdjustUp(HPDataType* arr,int size) { assert(arr); int sub size - 1;//取到数组最后一个节点的下标 int son sub; int father (son - 1) / 2;//找到它的父亲 while (son 0)//子节点下标是永远不为0的 { if (arr[son] arr[father])//如果子节点小于父亲那么进行交换 { HPDataType flag arr[son]; arr[son] arr[father]; arr[father] flag; son father;//交换完成父节点成为新的子节点即向上调整 father (son - 1) / 2;//向上更新父节点 } else//不满足更新条件退出函数 { return; } } } // 堆的插入 void HeapPush(Heap* hp, HPDataType x) { assert(hp); //判断是否需要扩容 if (hp-_capacity hp-_size) { int newcapacity (hp-_capacity 0) ? 4 : hp-_capacity * 2; HPDataType* newhp (HPDataType*)realloc(hp-_a, newcapacity * sizeof(HPDataType)); if (newhp NULL) { perror(realloc error!); return; } hp-_a newhp; hp-_capacity newcapacity; } //插入数据在叶子上 hp-_a[hp-_size] x; hp-_size; //向上调整 AdjustUp(hp-_a, hp-_size); }为了保持小堆的格式这里使用尾插并向上调整的算法这个算法中传入的形式参数是需要调整的数组和该数组有效元素个数具体逻辑请看注释。五、堆数据的删除//向下调整 //sub是调整的目标的下标目的是将较小的数据移到靠近根 void AdjustDown(HPDataType* arr, int size ,int sub) { //确保有左孩子满足最小的交换条件 while (sub * 2 1 size) { int secondson; int bigson; //确保有右孩子才能进行左右孩子的交换 if (sub * 2 2 size) { //假设左孩子小于右孩子 secondson 2 * sub 1; bigson secondson 1; //如果左孩子大于右孩子则交换左右孩子下标 if (arr[secondson] arr[bigson]) { int flag bigson; bigson secondson; secondson flag; } } else//没有右孩子那么小儿子就是左孩子 { secondson 2 * sub 1; } //开始向下调整 //如果父亲大于两个孩子之间最小的那一个那么久做一次交换 if (arr[secondson] arr[sub]) { HPDataType newdata arr[secondson]; arr[secondson] arr[sub]; arr[sub] newdata; sub secondson; } else//未满足交换条件退出函数 { return; } } } // 堆的删除 void HeapPop(Heap* hp) { assert(hp); assert(hp-_size); hp-_a[0] hp-_a[hp-_size - 1];//交换最后一个节点和第一个节点 hp-_size--;//删除节点原理同顺序表 //向下调整 AdjustDown(hp-_a, hp-_size,0); }因为删除没有插入那样简单直接删除掉根之后他下边的所有子节点便群龙无首因此我们不能直接删除根所以有大神使用将首尾位节点互换然后再向下调整根的数据的算法。因为互换的叶子节点肯定比互换前的根大所以需要向下调整互换后的根节点。至于为什么要比较左右节点的大小那是因为我们要把尽可能小的数据移动到尽可能靠近根的位置所以才需要比较左右节点的大小以满足小堆的格式。六、取堆顶的数据// 取堆顶的数据 HPDataType HeapTop(Heap* hp) { assert(hp); return hp-_a[0]; }七、求堆的数据个数// 堆的数据个数 int HeapSize(Heap* hp) { return hp-_size;//返回数据个数 }八、堆的判空// 堆的判空 int HeapEmpty(Heap* hp) { return hp-_size 0;//判断堆的数据个数是否等于0如果是返回非0否返回0 }九、测试代码void test() { Heap HP; HeapInit(HP); for (int i 0; i 100; i)//随机生成100个数据并插入进堆 { HeapPush(HP, rand()%1000); } while (!HeapEmpty(HP))//按照顺序取出数据 { printf(%d , HeapTop(HP)); HeapPop(HP); } HeapDestory(HP); } int main() { test(); return 0; }十、测试结果满足小堆的结构。

相关新闻

为什么OBS Studio成为全球千万用户选择的免费直播录制软件?

为什么OBS Studio成为全球千万用户选择的免费直播录制软件?

为什么OBS Studio成为全球千万用户选择的免费直播录制软件? 【免费下载链接】obs-studio OBS Studio - Free and open source software for live streaming and screen recording 项目地址: https://gitcode.com/GitHub_Trending/ob/obs-studio OBS Studio作…

2026/11/16 2:20:04 阅读更多 →
一文读懂flutter_chat_box架构:Flutter跨平台ChatGPT应用的设计之道

一文读懂flutter_chat_box架构:Flutter跨平台ChatGPT应用的设计之道

一文读懂flutter_chat_box架构:Flutter跨平台ChatGPT应用的设计之道 【免费下载链接】flutter_chat_box Flutter开发的和ChatGPT聊天的App,全平台支持 项目地址: https://gitcode.com/gh_mirrors/fl/flutter_chat_box flutter_chat_box是一个基于…

2026/11/16 2:20:05 阅读更多 →
Intelli IDEA:Cannot connect to already running IDE instance. Process xxx is still running的原因及解决方法

Intelli IDEA:Cannot connect to already running IDE instance. Process xxx is still running的原因及解决方法

1.查看自己的idea以及版本这里用WebStorm2023.2 为例,环境为windows;2. 原因是jetbrain启动时候会在 C:\Users\lingm\AppData\Roaming\JetBrains\WebStorm2023.2 目录下创建一个.lock文件,这个文件打开里面记录的是当前idea的进程号,每次idea…

2026/11/16 2:20:05 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/17 8:22:52 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/17 12:46:04 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/17 12:46:04 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/17 11:26:33 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/17 12:46:05 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/17 12:46:05 阅读更多 →

日新闻

周新闻

月新闻