堆的实现（C语言版）

发布时间：2026/7/29 9:09:29

堆的实现（C语言版）

堆的概念上个文章已经有过介绍了，简单的说就是一个完全二叉树，接下来我们主要来实现它。

一.选择实现方法

关于堆的实现，我们可以通过数组实现，也可以通过链表实现，由于链表过于浪费空间，而且我们可以简单的通过数组实现，就没必要用链表来实现，数组实现大家可能会想到是静态的还是动态的，我建议大家直接进行动态数组实现，之前顺序表我们两种都实现过了，而堆可以说和顺序表的结构体大体一样，这里就直接上手动态了。

二.实现过程

第一步：建立结构体

这一步和顺序表一样，就直接写出代码了。

//堆即是完全二叉树
//完全二叉树结构体定义
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

第二步：实现初始化接口和销毁接口

简单内容，直接上代码

//堆初始化接口定义
void HeapInit(HP* php)
{php->a = NULL;php->capacity = php->size = 0;
}
//堆销毁接口定义
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

第三步：（难点来了）实现堆的插入

我们这里是动态数组，所以，插入首先要进行的是扩容检查与扩容操作，这个是简单的，如下：

//空间开辟
if (php->size == php->capacity)
{int newcapacity = php->capacity==0 ?4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){exit(-1);}else{php->a = tmp;php->capacity = newcapacity;}
}

下面插入元素，由于是数组，我们先插入到数组的尾部，再进行调整，所以，这里插入直接插到尾部即可：

//插入
php->a[php->size] = x;
php->size++;

注意：数组下标与size的关系

插入完了，现在就要进行调整了，由于这是树，并且是完全二叉树，那么调整是不是只能用父与子来进行，肯定不能是堂兄弟调整，而父子有一个公式：

leftchild = parent*2+1;
childright = parent*2+2;parent=(child-1)/2;//不管左右孩子

所以我们就可以用一个向上调整法来实现，注意：你必须明确你是在建立大堆还是小堆，因为这里非常容易出错

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{//我们这里是实现小堆int parent = (child - 1) / 2;//由关系公式的//while (child>0)//终止条件while (parent >= 0)//两种写法{if (a[child] < a[parent])//由于建立小堆，孩子比父亲小，要交换位置{Swap(&a[child], &a[parent]);//交换位置函数child = parent;//原来的父亲位置是孩子现在位置，要再和上比较parent= (child - 1) / 2;//现在父亲位置}else{break;}}
}

总体看看：

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{//我们这里是实现小堆int parent = (child - 1) / 2;//由关系公式的//while (child>0)//终止条件while (parent >= 0)//两种写法{if (a[child] < a[parent])//由于建立小堆，孩子比父亲小，要交换位置{Swap(&a[child], &a[parent]);//交换位置函数child = parent;//原来的父亲位置是孩子现在位置，要再和上比较parent= (child - 1) / 2;//现在父亲位置}else{break;}}
}
//堆插入接口定义
void HeapPush(HP* php, HPDataType x)
{assert(php);//空间开辟if (php->size == php->capacity){int newcapacity = php->capacity==0 ?4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){exit(-1);}else{php->a = tmp;php->capacity = newcapacity;}}//插入php->a[php->size] = x;php->size++;//调整//向上调整法int child = php->size - 1;AdjustUp(php->a, child);
}

第四步：实现堆的删除

注意我们这里的堆删除是指堆顶，并非数组最后一个元素

首先我们要先进行首尾元素交换

Swap(&php->a[0], &php->a[php->size - 1]);

接下来尾删 

php->size--;

接下来由于堆顶元素与其他元素可能不满足堆的要求，所以我们要进行向下调整

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(HPDataType* a, int size, int parent)
{//注意我们这里是小堆奥//我们父与子交换条件是：父亲大于儿子，儿子可能有两个，所以我们要找小的，不然还要调整int child = parent*2+1;// 假设左孩子小，如果解设错了，更新一下while (child<size)//结束条件要想好{//假设错误，如果右孩子小if ((child + 1 < size) && (a[child + 1] < a[child])){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

第五步：实现取堆顶的元素

简单，直接上代码

//取出树根位置的数据定义
HPDataType HeapTop(HP* php)
{assert(php);assert(php->a);return php->a[0];
}

第六步：实现判断是否为空和确定堆元素个数

//堆中数据个数定义
size_t HeapSize(HP* php)
{assert(php);return php->size;
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

三.验证代码正确性

这个过程非常重要，本来应该是边实现边验证的，由于我这里要保证代码连贯性讲解，所以放一起来验证，但是希望大家还是边实现边验证的，不然，出现很多问题可能让你崩溃。

首先，我们来验证初始化，插入和销毁接口

void Print(HP* php, int n)
{for (int i = 0; i < n; i++){printf("%d ", php->a[i]);}printf("\n");
}
void test()
{HP s1;int a[] = {4,6,2,1,5,8,2,9};HeapInit(&s1);for (int i = 0; i < sizeof(a) / sizeof(int); ++i){HeapPush(&s1, a[i]);}Print(&s1, sizeof(a) / sizeof(int));HeapDestroy(&s1);
}
int main()
{test();return 0;
}

结果为堆，如下：

下面我们来验证堆的删除和取堆顶元素接口

void test()
{HP s1;int a[] = {4,6,2,1,5,8,2,9};HeapInit(&s1);for (int i = 0; i < sizeof(a) / sizeof(int); ++i){HeapPush(&s1, a[i]);}int k = 6;while (k--){printf("%d ", HeapTop(&s1));HeapPop(&s1);}HeapDestroy(&s1);
}
int main()
{test();return 0;
}

结果：

最后，我们在验证下判空吧

void test()
{HP s1;int a[] = {4,6,2,1,5,8,2,9};HeapInit(&s1);for (int i = 0; i < sizeof(a) / sizeof(int); ++i){HeapPush(&s1, a[i]);}while (!HeapEmpty(&s1)){printf("%d ", HeapTop(&s1));HeapPop(&s1);}printf("\n");HeapDestroy(&s1);
}
int main()
{test();return 0;
}

结果：

对于其他的大家可以自行验证，这里就不进行其他验证了。

四.代码完全版

这是Heap.c文件


#include "Heap.h"
void Print(HP* php, int n)
{for (int i = 0; i < n; i++){printf("%d ", php->a[i]);}printf("\n");
}//堆初始化接口定义
void HeapInit(HP* php)
{php->a = NULL;php->capacity = php->size = 0;
}
//堆销毁接口定义
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{//我们这里是实现小堆int parent = (child - 1) / 2;//由关系公式的//while (child>0)//终止条件while (parent >= 0)//两种写法{if (a[child] < a[parent])//由于建立小堆，孩子比父亲小，要交换位置{Swap(&a[child], &a[parent]);//交换位置函数child = parent;//原来的父亲位置是孩子现在位置，要再和上比较parent= (child - 1) / 2;//现在父亲位置}else{break;}}
}
//堆插入接口定义
void HeapPush(HP* php, HPDataType x)
{assert(php);//空间开辟if (php->size == php->capacity){int newcapacity = php->capacity==0 ?4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){exit(-1);}else{php->a = tmp;php->capacity = newcapacity;}}//插入php->a[php->size] = x;php->size++;//调整//向上调整法int child = php->size - 1;AdjustUp(php->a, child);
}
void AdjustDown(HPDataType* a, int size, int parent)
{//注意我们这里是小堆奥//我们父与子交换条件是：父亲大于儿子，儿子可能有两个，所以我们要找小的，不然还要调整int child = parent*2+1;// 假设左孩子小，如果解设错了，更新一下while (child<size)//结束条件要想好{//假设错误，如果右孩子小if ((child + 1 < size) && (a[child + 1] < a[child])){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
// 规定删除堆顶（根节点）
void HeapPop(HP* php)
{assert(php);//首尾交换Swap(&php->a[0], &php->a[php->size - 1]);//尾删php->size--;//向下调整法AdjustDown(php->a, php->size, 0);
}//取出树根位置的数据定义
HPDataType HeapTop(HP* php)
{assert(php);assert(php->a);return php->a[0];
}
//堆中数据个数定义
size_t HeapSize(HP* php)
{assert(php);return php->size;
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

Heap.h文件：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//堆即是完全二叉树
//完全二叉树结构体定义
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//堆初始化接口声明
void HeapInit(HP* php);
//堆销毁接口声明
void HeapDestroy(HP* php);
//堆插入接口声明
void HeapPush(HP* php, HPDataType x);
// 规定删除堆顶（根节点）
void HeapPop(HP* php);
//取出树根位置的数据声明
HPDataType HeapTop(HP* php);
//堆中数据个数声明
size_t HeapSize(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);

最后，这里给大家提一个问题，如果我是实现大堆呢？基于上述代码，应该如何改动呢？

小编祝福大家：Merry Christmas,拜拜！

相关新闻

虚幻学习笔记22—C++同步和异步加载

虚幻学习笔记22—C++同步和异步加载

一、前言 之前提到的静态和动态加载都是同步的加载&#xff0c;同时其中的引用基本都是硬引用。如果资源比较大的话会出现卡顿的现象&#xff0c;下面将介绍一种异步加载的方式。同时&#xff0c;还将介绍一种区别与之前的Load的方法。 在说明同步和异步加载之前需要先讲一下虚…

2026/7/27 11:31:14
[Linux] Mysql数据库中的用户管理与授权

[Linux] Mysql数据库中的用户管理与授权

一、登录用户的管理 1.1 查看用户密码的信息 用户信息存放在 mysql 数据库下的 user 表&#xff08;MySQL 服务下存在一个系统自带的 mysql 数据库&#xff09;。 use mysql ; show tables; desc user; 查看密码信息的命令&#xff1a; 能看到密码信息&#xff1a;是经过加…

2026/7/27 18:07:15
c# OpenCvSharp透视矫正六步实现透视矫正（八）

c# OpenCvSharp透视矫正六步实现透视矫正（八）

透视矫正,引用文档拍照扫描&#xff0c;相片矫正这块。 读取图像Cv2.ImRead();预处理&#xff08;灰度化&#xff0c;高斯滤波、边缘检测&#xff09;轮廓检测&#xff08;获取到最大轮廓&#xff09;获取最大面积轮廓的四个顶点标识最小矩形坐标透视矫正显示 完整代码 // 1、…

2026/7/25 4:09:14

最新新闻

Docker Compose 前后端部署踩坑实录：3 个坑让我的容器反复 Exit(1)

Docker Compose 前后端部署踩坑实录：3 个坑让我的容器反复 Exit(1)

技术栈&#xff1a;Vue 3 Python/Gunicorn MySQL Nginx Docker Compose 部署环境&#xff1a;阿里云 Ubuntu 阅读时长&#xff1a;约 8 分钟前言 最近在阿里云上用 Docker Compose 部署一个前后端分离项目&#xff0c;前端 Vue 打包后丢给 Nginx&#xff0c;后端是 Python …

2026/7/29 9:09:01
嵌入式按键消抖进阶：从基础原理到多层抗干扰设计

嵌入式按键消抖进阶：从基础原理到多层抗干扰设计

1. 从“按键消抖”到“消抖中的消抖”&#xff1a;一个被忽视的工程细节 在嵌入式开发或者任何涉及机械按键的电子项目中&#xff0c;“按键消抖”是一个老生常谈的话题。任何一个合格的工程师都知道&#xff0c;由于按键的机械结构特性&#xff0c;在按下和释放的瞬间&#xf…

2026/7/29 9:08:39
单片机掉电数据保存方案：从EEPROM/FLASH选型到软硬件实现

单片机掉电数据保存方案：从EEPROM/FLASH选型到软硬件实现

1. 项目概述&#xff1a;为什么单片机需要“临终关怀”&#xff1f;在嵌入式开发领域&#xff0c;尤其是涉及工业控制、智能仪表、消费电子等场景时&#xff0c;我们经常会遇到一个看似简单却至关重要的需求&#xff1a;当设备意外断电时&#xff0c;如何确保关键数据不丢失&am…

2026/7/29 9:08:39
钕磁铁在硬件调试中的实战应用：从EMI排查到故障定位

钕磁铁在硬件调试中的实战应用：从EMI排查到故障定位

1. 项目概述&#xff1a;当“万磁王”遇上技术宅 最近在折腾一个老项目&#xff0c;遇到了一个让我和团队都头疼不已的问题&#xff1a;一块核心的电路板在调试时频繁出现信号异常&#xff0c;时好时坏&#xff0c;排查了整整两天&#xff0c;从代码到电源&#xff0c;从传感器…

2026/7/29 9:08:39
CH582F蓝牙MCU低功耗实战：RTC定时唤醒与Sleep模式深度优化

CH582F蓝牙MCU低功耗实战：RTC定时唤醒与Sleep模式深度优化

1. 项目概述&#xff1a;低功耗设计的核心——RTC唤醒在嵌入式开发&#xff0c;尤其是电池供电的物联网设备开发中&#xff0c;功耗控制是决定产品续航能力乃至成败的关键。很多开发者&#xff0c;尤其是从STC、STM32等平台转过来的朋友&#xff0c;常常会问&#xff1a;沁恒家…

2026/7/29 9:08:39
企业AI品牌代言人构建指南：从数据到部署

企业AI品牌代言人构建指南：从数据到部署

1. 为什么企业需要AI品牌代言人&#xff1f; 去年服务某快消品牌时&#xff0c;他们的市场总监向我吐槽&#xff1a;每次新品上市&#xff0c;光是协调不同渠道的内容风格就要耗费两周。公众号要活泼、官网要专业、电商详情页要突出卖点...这种割裂感在消费者端形成了认知混乱。…

2026/7/29 9:08:39

日新闻

自律同行，突破无界！NANK南卡正式官宣曾舜晞成为品牌代言人

自律同行，突破无界！NANK南卡正式官宣曾舜晞成为品牌代言人

近日&#xff0c;国际专注开放式技术研发的声学品牌Nank南卡&#xff0c;正式官宣实力艺人曾舜晞担任品牌代言人。消息一经发出便轰动全网。为什么耳机品牌不选择流量明星、老牌歌手&#xff1f;而且是选择曾舜晞&#xff1f;让我们一起来探索一下&#xff01;比起短期的流量&a…

2026/7/29 0:00:42
【RT-DETR多模态创新改进】CVPR 2025 | 独家特征融合创新改进篇 | 引入RLAB残差线性注意力模块，有效融合并强调多尺度特征，多种改进点，适合红外与可见光融合目标检测任务，有效涨点

【RT-DETR多模态创新改进】CVPR 2025 | 独家特征融合创新改进篇 | 引入RLAB残差线性注意力模块，有效融合并强调多尺度特征，多种改进点，适合红外与可见光融合目标检测任务，有效涨点

一、本文介绍 🔥本文在RT-DETR多模态融合目标检测中引入RLAB残差线性注意力模块，可在不同模态特征交互阶段进行多次残差细化，使可见光、红外等特征在尺度、语义和空间位置上更好对齐；随后将细化特征与解码器输出拼接并生成Q、K、V，通过线性注意力自适应强化关键通道、目…

2026/7/29 0:00:42
AI编程系列02：合并知识功能，给 AI 问数和 RAG 场景打基础

AI编程系列02：合并知识功能，给 AI 问数和 RAG 场景打基础

AI编程系列02&#xff1a;合并知识功能&#xff0c;给 AI 问数和 RAG 场景打基础 在上一期「AI编程系列」中&#xff0c;我们学习了如何构建一个基础的 AI 问答系统&#xff0c;通过简单的输入输出让模型回应问题。但现实世界中的 AI 应用往往需要处理更复杂的场景&#xff1a;…

2026/7/29 0:00:42

周新闻

Apex英雄目标检测数据集 深度学习框架YOLO如何训练APEX数据集

Apex英雄目标检测数据集 深度学习框架YOLO如何训练APEX数据集

Apex检测数据集数据集详情检测类别&#xff1a; allies enemy tag图片总量&#xff1a;7247张训练集&#xff1a;5139张验证集&#xff1a;1425张测试集&#xff1a;683张标注状态&#xff1a;全部已标注&#xff0c;即拿即用数据格式&#xff1a;支持YOLO格式及其他格式&#…

2026/7/28 8:40:21
智慧飞行 大疆无人机一站式智能管控平台/支持大疆机场/私有化部署 从航线规划、自动飞行、AI识别到数据管理，一个平台全搞定

智慧飞行 大疆无人机一站式智能管控平台/支持大疆机场/私有化部署 从航线规划、自动飞行、AI识别到数据管理，一个平台全搞定

智慧飞行-大疆无人机一站式智能管控平台/支持大疆机场/私有化部署 企业级全域智能无人机一体化管控平台源码&#xff01; 专为电力巡检、安防监控、应急救援、测绘勘察等行业打造&#xff0c;让您的无人机舰队实现 “无人化、自动化、智能化” 管理&#xff01; &#x1f3af; …

2026/7/28 6:30:42
揭秘ChatGPT+Mathematica协同教学：为什么92%的初学者在72小时内建立函数直觉？

揭秘ChatGPT+Mathematica协同教学：为什么92%的初学者在72小时内建立函数直觉？

更多请点击&#xff1a; https://codechina.net 第一章&#xff1a;AI帮助理解数学概念 人工智能正以前所未有的方式重塑数学学习的路径。通过自然语言处理与符号计算的深度融合&#xff0c;AI不仅能解析抽象定义&#xff0c;还能将定理、证明和几何直觉转化为可交互、可验证的…

2026/7/28 9:00:08

月新闻

[C++]内存管理：串顺序存储的内存回收

[C++]内存管理：串顺序存储的内存回收

在串&#xff08;字符串&#xff09;的顺序存储中&#xff0c;内存回收的方式取决于字符串的存储方式以及所使用的编程语言和相关库。以下以 C 为例进行说明&#xff0c;因为 C 对内存管理有较为直接的控制。 1. 基于 char 数组的串顺序存储 如果使用普通的 char 数组来存储字…

2026/7/29 2:28:15
移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试：先控制变量，再比较优化是否真的省电 摘要：功耗测试最容易犯的错误，是拿两次不同温度、不同亮度、不同场景的平均功率直接比较。本文给出一套可复现的游戏功耗测试方法，覆盖引擎特性验证、版本回归和黑盒体验测试，并说明如何把功耗与帧率、温控、CPU/G…

2026/7/29 2:28:16
足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

本文是“足球口袋教练 HarmonyOS 离线应用实战”系列第 3 篇。示例项目是一个 HarmonyOS / ArkTS / ArkUI 编写的离线足球训练助手&#xff0c;围绕真实页面、真实截图和可复现操作展开。 本篇要解决的问题 训练 App 的首页不能只展示欢迎语&#xff0c;它要解决“我现在该点哪…

2026/7/28 11:58:14