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

【数据结构初阶】--二叉树(二)

news 2025/7/27 4:18:23

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：在上篇博客中我们了解了树和二叉树的一些知识点。那么我们今天这篇博客主要是来带大家实现一下堆(一种特殊的二叉树) ，还是和之前一样，我们先分几个部分来实现，最后再展示总体的代码

目录

一.堆的概念与结构

 二.堆的初始化和销毁

堆的初始化：

堆的销毁： 

三.堆的插入数据(含向上调整算法的实现) 

向上调整算法：

三. 堆的删除数据(含向下调整算法)

向下调整算法：

四.堆的取堆顶 

五.堆排序的实现

版本一(test.c文件中)：

版本二(test.c文件中)：更推荐的版本

 六.代码展现

Heap.h：

Heap.c：

test.c：

一.堆的概念与结构

 --如果有一个关键码的集合K={k_{0},k_{1},k_{2},......,k_{n-1}}，把它所有的元素按照完全二叉树的顺序存储方式存储，这里堆的底层实现其实也就是一个数组。我们堆分为小堆和大堆。我们将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或者小根堆。

堆具有以下性质： 

  • 堆中某个结点的值总是不大于或者不小于其父结点的值
  • 堆总是一颗完全二叉树
  • 堆顶是最值(最大值或最小值)

二叉树性质 

--对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：

  1. 若i>0，i的位置结点的双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
  2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n，则无左孩子
  3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n，则无右孩子

堆的结构定义如下： 

typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;int capacity;
}HP;

 二.堆的初始化和销毁

堆的初始化：

//初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = 0;php->capacity = 0;
}

初始化操作的实现和顺序表操作差不多，初始数组置为空，size和capacity都设置为0 

堆的销毁： 

//销毁
void HPDestory(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

销毁之前先检查数组为不为空，不为空就释放掉然后置空，并把size和capacity也重新置为空

三.堆的插入数据(含向上调整算法的实现) 

--我们实现堆的插入大致思路都跟顺序表一样，但是在尾部插入一个数据后，原来的堆就改变了，我们需要把插入的数据调整到对应的位置上，我们先来看个图片吧(以大堆为例)

--根据图示操作我们来实现向上调整算法的代码

向上调整算法：

//向上调整
void AdjustUp(HPDataType*arr, int child)
{assert(arr);int parent = (child - 1) / 2;while (child > 0){//大堆：>//小堆：<if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);child = parent;parent= (child - 1) / 2;}else{break;}}
}

 --这里我实现的是大堆的，大堆就是孩子大于父亲就交换，小堆与之相反。这里的循环就是当孩子结点为0的时候结束，即走到了根节点了。

其中交换函数的实现我就直接放在这里了，很简单：

//交换
void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}

我们再接着来看看堆的插入数据的代码：

//往堆里面插入数据
void HPPush(HP* php, HPDataType x)
{//检查空间是否足够//不够就扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr,newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}//够就直接插入php->arr[php->size++] = x;//向上调整AdjustUp(php->arr, php->size - 1);//因为前面size++了，所有传的是size-1
}

我们这里实现的插入(断言可以加一下)，首先检查空间是否足够，不够就增容，这个操作大家应该都不陌生。空间足够我们就直接插入数据，但是插入完后我们会发现不一定还是大堆了，所有我们需要调用向上调整算法，这里传数据为啥是要-1我在代码中有注释，大家可以自己看看

--为了便于观察我们实现一个打印的接口，和顺序表是一样的方式 

//打印
void HPPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}

test.c： (测试中的数据和画图里的不一样)

#include"Heap.h"void test1()
{//初始化HP p;HPInit(&p);//插入HPPush(&p, 15);HPPush(&p, 10);HPPush(&p, 35);HPPush(&p, 80);HPPush(&p, 70);HPPush(&p, 25);HPPrint(&p);//销毁HPDestory(&p);
}int main()
{test1();
}

--测试完成，没有问题，插入数据后打印出了一个大堆，退出码为0

三. 堆的删除数据(含向下调整算法)

--我们实现堆的删除需要的是头部操作，如果跟顺序表一样去移动数据的话会改变掉堆的结构，所以我们可以先交换首尾数据，然后再把尾上的数据删掉。然后再通过向下调整算法将堆再次调整成一个大堆

--根据图示操作，我们来实现向下调整算法

向下调整算法：

//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{assert(arr);int child = 2 * parent + 1;while (child < n){//child+1也小于n//后面的小堆就是取小的，大堆取大的孩子if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆：>   小堆：<if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}

这里实现的是大堆的，至于小堆如何实现，大家应该看注释就知道了 

--有了这个之后，我们再实现一个判空的函数之后就可以来实现删除了，判空的代码如下：

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

删除数据(栈顶操作)：

//删除(堆顶操作)
void HPPop(HP* php)
{assert(!HPEmpty(php));//首尾交换swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//向下调整AdjustDown(php->arr, 0, php->size);
}

先判断不为空，然后交换首尾，直接--size删掉，再通过向下调整算法把删除一个数据后的堆重新调整成大堆。  

四.堆的取堆顶 

 --堆的取栈堆顶操作(不为空才能取)就很简单了，我们直接来实现看看代码

//取堆顶
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

--这里再补充一个求堆的数据个数的接口，也很简单

//求size
int HPSize(HP* php)
{assert(php);return php->size;
}

--在实现了取堆顶后，我们通过测试文件看一个很意思的操作 

test.c： 

#include"Heap.h"void test1()
{//初始化HP p;HPInit(&p);//插入HPPush(&p, 15);HPPush(&p, 10);HPPush(&p, 35);HPPush(&p, 80);HPPush(&p, 70);HPPush(&p, 25);HPPrint(&p);//遍历，取顶部打印再出堆while (!HPEmpty(&p)){HPDataType top = HPTop(&p);printf("%d ", top);HPPop(&p);}//我们会发现是有序的，但这个只是将数据在终端顺序打印出，那我们能不能试着实现堆排序呢//销毁HPDestory(&p);
}int main()
{test1();
}

--我们看打印出来的第二行发现，循环这个取顶部打印出堆的操作会将大堆有序(降序)的打印出来

但是这里呢我们对比之前学的冒泡排序其实我们只是将数据在终端顺序打印出，那我们能不能试着实现堆排序呢，我们接着往下看

五.堆排序的实现

--我们堆排序的实现，其实有两种方式，但是呢第一种并不是真正的堆排序，因为它需要使用堆这个数据结构，但是第二种只是需要堆这个数据结构的思想。而且真正的堆排序建大堆是升序，小堆是降序。而第一种主要是模仿我们上面那个遍历取顶操作实现出来的，大堆反而是降序。但是我们还是把两种都一起看一下

版本一(test.c文件中)：

#include"Heap.h"//堆排序--这不是真正的堆排序，而是利用了堆这个数据结构来实现的排序
void HeapSort1(int* arr, int n)
{HP sp;HPInit(&sp);for (int i = 0; i < n; i++){HPPush(&sp, arr[i]);}int i = 0;while (!HPEmpty(&sp)){HPDataType top = HPTop(&sp);arr[i++] = top;HPPop(&sp);}
}int main()
{int arr[6] = { 30,56,25,15,70,10 };printf("排序之前：\n");for (int i = 0; i < 6; i++){printf("%d ", arr[i]);}printf("\n");HeapSort1(arr, 6);printf("排序之后：\n");for (int i = 0; i < 6; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

这里就是先初始化一个堆，然后把数组里的元素插入到堆中，再利用循环遍历重复(取顶部数据放回数组后++到下一个后，删掉(弹出了堆)的操作)。由于是大堆所以每次取顶部取的都是当前堆中最大的数据，最后排出来的就是降序，这里还是特别注意一下，这严格来说不算真正的堆排序，它必须使用堆这个数据结构，而且真正的堆排序应该是大堆排升序，小堆排降序

版本二(test.c文件中)：更推荐的版本

#include"Heap.h"//用堆的思想来实现排序--我建的大堆，所以升序
void HeapSort(int* arr, int n)
{//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//实现排序int end = n - 1;while (end>0){//交换，因为是大堆所以栈顶是最大值，每次将最大值放到最后swap(&arr[0], &arr[end]);//再向下调整,使除了已经按最大放在最后的以外其它的继续成为一个大堆AdjustDown(arr, 0, end);end--;}
}int main()
{/*test1();*/int arr[6] = { 30,56,25,15,70,10 };printf("排序之前：\n");for (int i = 0; i < 6; i++){printf("%d ", arr[i]);}printf("\n");HeapSort(arr, 6);printf("排序之后：\n");for (int i = 0; i < 6; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

我们可以看出这个方法实现出来的就是非常标准的了，大堆排出来为升序。具体思路其实就是先利用向下调整算法建堆，从最底下的一个根结点开始(即(n-1-1)/2) ,将第一个排好后直接减减就能接着排下一个，最后到0都建完后，整体就是一个堆了。后续先定义一个end=n-1的下标，然后遍历【重复交换首尾，向下调整(注意这里就是正常传了，父结点刚开始为0，然后是数组大小，我们传end就行，不会影响已经放到最后的)，end--的操作)，最后end为0的时候结束】此时堆已经是一个从小到大的顺序了，因为我们每次的交换其实就是把当前顶部最大的放在最后，之后下次就不会再排它了。

--我这里实现的这个大堆实现升序就不画图展示出来了，但是还是给大家分享一个用小堆实现降序的画图过程

 六.代码展现

Heap.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;int capacity;
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDestory(HP* php);//打印
void HPPrint(HP* php);//交换
void swap(int* a, int* b);//向上调整
void AdjustUp(HPDataType* arr, int child);//向下调整
void AdjustDown(HPDataType* arr, int parent, int n);//往堆里面插入数据
void HPPush(HP* php, HPDataType x);//判空
bool HPEmpty(HP* php);//删除(堆顶操作)
void HPPop(HP* php);//取堆顶
HPDataType HPTop(HP* php);//求size
int HPSize(HP* php);

Heap.c：

#include"Heap.h"//初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = 0;php->capacity = 0;
}//销毁
void HPDestory(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}//打印
void HPPrint(HP* php)
{assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}
//交换
void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//向上调整
void AdjustUp(HPDataType*arr, int child)
{assert(arr);int parent = (child - 1) / 2;while (child > 0){//大堆：>//小堆：<if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);child = parent;parent= (child - 1) / 2;}else{break;}}
}//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{assert(arr);int child = 2 * parent + 1;while (child < n){//child+1也小于n//后面的小堆就是取小的，大堆取大的孩子if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆：>   小堆：<if (arr[child] > arr[parent]){swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}//往堆里面插入数据
void HPPush(HP* php, HPDataType x)
{//检查空间是否足够//不够就扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr,newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newcapacity;}//够就直接插入php->arr[php->size++] = x;//向上调整AdjustUp(php->arr, php->size - 1);//因为前面size++了，所有传的是size-1
}//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//删除(堆顶操作)
void HPPop(HP* php)
{assert(!HPEmpty(php));//首尾交换swap(&php->arr[0], &php->arr[php->size - 1]);php->size--;//向下调整AdjustDown(php->arr, 0, php->size);
}//取堆顶
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}//求size
int HPSize(HP* php)
{assert(php);return php->size;
}

test.c：

#include"Heap.h"void test1()
{//初始化HP p;HPInit(&p);//插入HPPush(&p, 15);HPPush(&p, 10);HPPush(&p, 35);HPPush(&p, 80);HPPush(&p, 70);HPPush(&p, 25);HPPrint(&p);//遍历，取顶部打印再出堆while (!HPEmpty(&p)){HPDataType top = HPTop(&p);printf("%d ", top);HPPop(&p);}//我们会发现是有序的，但这个只是将数据在终端顺序打印出，那我们能不能试着实现堆排序呢//销毁HPDestory(&p);
}
//堆排序--这不是真正的堆排序，而是利用了堆这个数据结构来实现的排序
void HeapSort1(int* arr, int n)
{HP sp;HPInit(&sp);for (int i = 0; i < n; i++){HPPush(&sp, arr[i]);}int i = 0;while (!HPEmpty(&sp)){HPDataType top = HPTop(&sp);arr[i++] = top;HPPop(&sp);}
}//用堆这个数据结构的思想来实现排序--我建的大堆，所以升序
void HeapSort(int* arr, int n)//n*logn
{//向下调整算法建堆-o(n)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//实现排序,n*lognint end = n - 1;while (end>0){//交换，因为是大堆所以栈顶是最大值，每次将最大值放到最后swap(&arr[0], &arr[end]);//再向下调整,使除了已经按最大放在最后的以外其它的继续成为一个大堆AdjustDown(arr, 0, end);end--;}
}int main()
{/*test1();*/int arr[6] = { 30,56,25,15,70,10 };printf("排序之前：\n");for (int i = 0; i < 6; i++){printf("%d ", arr[i]);}printf("\n");HeapSort(arr, 6);printf("排序之后：\n");for (int i = 0; i < 6; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

往期回顾：

【数据结构初阶】--双向链表(二)

【数据结构初阶】--栈和队列(一)

【数据结构初阶】--栈和队列(二)

【数据结构初阶】--树和二叉树先导篇

结语：本篇博客中我们一起实现了堆这个数据结构，还了解了堆排序的思想和代码实现。综合来看这里的难度要比前面几个结构都难，但是学会了之后的提升也是更明显的。在后续的博客中，我们还会证明向下调整和向上调整算法建堆的复杂度证明以及用链式结构来实现二叉树，大家可以很好的感觉到递归的暴力美学。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。

http://www.lryc.cn/news/598820.html

相关文章：

  • FreeSWITCH 简单图形化界面45 - 收集打包的一些TTS
  • 内网IM：BeeWorks私有化部署的安全通讯解决方案
  • 安全插座项目规划书
  • 【VSCode】复制到下一行快捷键
  • 2024年ASOC SCI2区TOP，基于强化学习教与学优化算法RLPS-TLBO+风电场布局优化，深度解析+性能实测
  • Go基础教程 从零到英雄：30分钟掌握Go语言核心精髓
  • Go语言管道Channel通信教程
  • 黑马点评系列问题之p44实战篇商户查询缓存 jmeter如何整
  • 2025.7.24 01背包与动态规划复习总结
  • 【Oracle】Oracle权限迷宫破解指南：2步定位视图依赖与授权关系
  • MySQL常见命令
  • 多线程 Reactor 模式
  • hcip思维导图（1）
  • GaussDB 数据库架构师(八) 等待事件概述-1
  • 阿里云ECS坑之dnf-makecache系统软件更新检测服务
  • 解决postgresql连接数不足
  • 五分钟了解Java 中的锁
  • SQL基础⑪ | 约束
  • JavaScript 中的 structuredClone() 如何彻底改变你的对象复制方式
  • Android LiveData 全面解析：原理、使用与最佳实践
  • Windows 10 远程桌面(RDP)防暴力破解脚本
  • Android 与 Windows 文件路径的设计差异
  • Android Camera createCaptureSession
  • 教程：如何通过代理服务在国内高效使用 Claude API 并集成到 VSCode
  • DGMR压缩技术：让大规模视觉Transformer模型体积减半而性能不减
  • FastAPI中间件
  • iview 部分用法
  • 锁定锁存器 | 原理 / 应用 / 时序
  • 哈希表模拟实现
  • JVM 垃圾收集器CMS和G1