手撕数据结构 —— 堆（C语言讲解）

embedded/2024/10/17 20:28:36/

目录

1.堆的认识

什么是堆

堆的性质

2.堆的存储

3.堆的实现

Heap.h中接口总览

具体实现

堆结构的定义

初始化堆

销毁堆

堆的插入

堆的向上调整算法

堆的插入的实现

堆的删除

堆的向下调整算法

堆的删除的实现 

使用数组初始化堆

获取堆顶元素

获取堆中的数据个数

判断堆是否为空

打印堆中的元素

4.堆的应用

堆排序

堆排序的思想

堆排序的实现

实现步骤

堆的创建

堆排序测试代码

TOP-K问题

什么是top-k问题

解决top-k问题的思路

堆排序示例代码

5.堆的实现代码附录

Heap.h

Heap.c

1.堆的认识

什么是堆

想要弄清楚什么是堆，首先需要了解二叉树的相关知识，推荐阅读数据结构——树和二叉树简介。

堆分为大根堆和小根堆：

  • 大根堆：如果一棵完全二叉树中除了叶子结点的每个结点的值都大于其左右孩子，则这棵完全二叉树就叫做大根堆。大根堆的对顶元素是这棵树中的最大元素。

  • 小根堆：如果一棵完全二叉树中除了叶子结点的每个结点的值都小于其左右孩子，则这棵完全二叉树就叫做小根堆。小根堆的堆顶元素是整棵树的最小元素。

堆的性质

1、堆总是一棵完全二叉树

2、大根堆中每个结点的值总是不大于其父结点的值，小根堆中每个结点的值总是不小于其父结点的值。

2.堆的存储

堆是完全二叉树的特殊情况，完全二叉树是二叉树的特殊情况，二叉树的存储可以用顺序结构存储和链式结构存储。完全二叉树的结点从上到下，从左到右是依次连续的，更适合用顺序结构存储，因为不会有空间的浪费，所以堆的存储是用顺序结构存储的，也就是使用数组存储。

使用数组存储堆的具体做法如下：

  • 对每个结点从上到下，从左到右依次从0开始编号。
  • 结点编的号对于数组的下标。
  • 数组下标对应的空间中保存结点的数据。

3.堆的实现

堆的实现，我们主要实现Heap.h和Heap.c文件，Heap.h中存放声明，Heap.c中存放定义。

(文末附源码！)

Heap.h中接口总览

具体实现

堆结构的定义

我们使用数组来存储堆，并且采用动态的数组，所以堆结构的定义如下：

  • a指向底层的数组空间。
  • size记录有效数据的个数。
  • capacity记录空间的大小，当空间不够时自动扩容。

初始化堆

当我们定义堆结构之后，在使用堆结构之前，需要将堆进行初始化：

  • 首先需要判断指向堆的指针是否为空，该指针不能为空。后面涉及该指针都需要判空，将不再赘述。
  • a初始化为空指针。
  • size和capacity都初始化为0。

销毁堆

销毁堆，就是释放其结构，释放底层的数组空间，并将指向数组空间的指针置空，size和capacity都置为0即可。

堆的插入

我们采用数组存储堆，想堆中插入数据其实就是向数组中插入数据，在数组的尾部插入的时间复杂度是O(1)，非常高效，所以堆的插入也采用尾插，但是，插入数据之后，堆结构有可能被破坏。

如下图：向堆中插入-1，此时插入的节点的值小于其父结点的值，不符合小根堆的特点，破坏了堆的结构，所以需要进行调整。我们采用堆的向上调整算法。

堆的向上调整算法

向上调整的前提：前面的数据是堆。

算法步骤如下：

  • 1.将当前结点的值和父结点的值比较，判断是否符合当前堆的性质。
  • 2.如果满足则无需调整，不满足则和父结点的值交换。
  • 3.交换完之后重复1过程。

向上调整代码如下： 

向上调整算法时间复杂度分析：堆的向上调整算法在最优情况下不需要调整，在最坏情况下需要调整树的高度-1次。所以时间复杂度是O(logN)。

堆的插入的实现

在堆中插入数据可以分如下几步实现：

  • 1.首先判断是否需要扩容。
  • 2.在数组空间的末尾插入数据，记得将size++。
  • 3.然后进行向上调整。

堆的删除

删除堆的元素的时候，删除的是堆顶的元素，这是堆的特点。堆的存储采用的是数组空间，删除堆中的堆顶元素删除的就是数组空间中的第一个元素，数组进行头删的时间复杂度是O(N)，效率不高，于是，我们采用替换法删除，首先将堆数组的第一个元素和最后一个元素删除，然后删除最后一个元素即可。

但是，这里有一个和堆的插入相同的问题，删除元素之后，堆的结构可能会被破坏。这就需要使用向下调整算法来调整堆的结构了。

堆的向下调整算法

向下调整的前提：左右子树是堆。

算法步骤如下：

  • 1.计算出左孩子的下标。
  • 2.如果是小堆，找出两个孩子中小的那个；如果是大堆，找出两个孩子中大的那个。
  • 3.判断父结点和选择的孩子结点是否满足当前堆的性质。
  • 4.如果满足则不需要调整了，标识当前二叉树符合堆的性质。
  • 5.不满足则交换，并且更新父结点和孩子结点的值，再次调整，重复2步骤。

向下调整代码如下： 

向下调整算法时间复杂度分析：堆的向下调整算法在最优情况下不需要调整，在最坏情况下需要调整树的高度-1次。所以时间复杂度是O(logN)。 

堆的删除的实现 

删除堆顶元素可以分如下几步进行：

  • 1.将第一个元素和最后一个元素交换。
  • 2.将size--，表示有效数据减1。
  • 3.进行向下调整，保持堆的结构。

使用数组初始化堆

在使用堆的时候，我们需要使用数据来初始化堆，也就是建堆。建堆可以使用向上调整建堆，也可以使用向下调整建堆，这里我们使用向上调整建堆。

向上调整建堆的步骤：

  • 1.动态申请一块堆空间，并判断申请是否成功。
  • 2.size 和 capacity都置为待初始化数组的大小。
  • 3.把数据从待拷贝数组拷贝到堆数组中。
  • 4.从第二个元素开始，逐元素进行向上调整建堆。

向上调整建堆代码如下：

获取堆顶元素

堆顶元素就是底层数组空间中的第一个元素，直接返回下标为0的元素即可。

获取堆中的数据个数

size就是用来记录有效元素个数的，直接返回size即可。

判断堆是否为空

当size == 0的时候，说明堆中没有元素，直接判断size是否等于0即可。

打印堆中的元素

遍历打印即可。

4.堆的应用

堆的应用主要有堆排序和解决TOP-K问题。

堆排序

堆排序的思想

参考堆删除的思想来排序，删除堆顶元素的时候，我们使用的是替换法删除，也就是将堆顶元素放到当前数组末尾，每次选择的是堆中当前的最大or最小元素。相当于每次都能选出一个值，从后往前填入如数组。

  • 如果是大堆，每次选出的数据就是当前堆中最大的元素，从数组后面往前填入数组，排出来的数据是升序的。
  • 如果是小堆，每次选出的数据就是当前堆中最小的元素，从数组后面往前填入数组，排出来的数据是降序的。

所以，如果我们想排升序，建堆的时候，应该建立大堆；如果我们想排降序，建堆的时候，应该建立小堆。

堆排序的实现

实现步骤
  • 先建堆。排升序，建立大堆；排降序，建立小堆。
  • 对堆结构进行向下调整，每次选出一个数放在正确的位置。
堆的创建

建堆有两种方法，一种是向上调整建堆，一种是向下调整建堆。

向上调整建堆：向上调整的前提是前面的数据是堆，所以，数据应该从上往下，从做往右依次进行向上调整。一个数据通过向上调整建堆最多调整树的高度-1次，也就是logN，一共N个数据，所以向上调整建堆的时间复杂度是O(N*logN)。

向下调整建堆：向下调整的前提是左右子树是堆，也就是后面的数据是堆，因为，叶子结点没有孩子，所以应该从倒数第一个非叶子结点开始进行向下调整。

向下调整建堆的时间复杂度为O(N)，要优于向上调整建堆。 

堆排序测试代码
#include <iostream>
using namespace std;typedef int HPDataType;
typedef struct Heap
{HPDataType* a;  // 指向底层的数组空间 int size;       // 存储的有效数据个数 int capacity;   // 数组空间的容量大小 
}HP;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){if (a[child] < a[parent])    // 此处比较符号控制大小堆的创建 {Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 找出小的那个孩子if (child + 1 < n && 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 HeapSort(int* a, int n)
{// 向上调整建堆 排升序，建大堆  排降序，建小堆 // O(N*logN)/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*/// 向下调整建堆// O(N)for (int i = (n-1-1)/2; i >= 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}int main()
{int a[] = { 2,5,3,7,4,8,6 };HeapSort(a, sizeof(a) / sizeof(int));int i = 0;while(i < 7){cout << a[i] << ' ';i++;} return 0;
}

堆排序时间复杂度分析：向下调整选出一个正确的数的时间复杂度是O(logN)，一共有N个数，所以时间复杂度是O(N*log(N))。 

TOP-K问题

什么是top-k问题

top-k问题就是求数据集合中的前k个最大元素or最小元素。（一般数据量都比较大）比如：游戏中的前10名玩家……等等大规模的数据中找最小的or最大的k个元素的问题都是top-k问题。

解决top-k问题的思路

解决top-k问题最直接的方法就是排序，但是当数据量非常大的时候，无法全部加载到内存中的时候，就需要使用堆来解决。具体思路如下：

  • 1.用数据集合中的前k个来建堆。求前k个最大，建小堆；求前k个最小，建大堆。
  • 2.用剩余的n-k个元素依次与堆顶元素比较。如果建的是大堆，当数据比堆顶元素小的时候替换堆顶元素；如果建的是小堆，当数据比堆顶元素大的时候替换堆顶元素。

将剩余的n-k个元素比较完之后，堆中剩余的就是前k个最小or最大的元素。

堆排序示例代码

#include <stdlib.h>
#include <time.h>void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 前k个数建小堆for (int i = (k-2)/2; i >=0 ; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){// 替换你进堆minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");free(minheap);fclose(fout);
}void CreateNDate()
{// 造数据int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{CreateNDate();PrintTopK("data.txt", 5);return 0;
}

5.堆的实现代码附录

Heap.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
#include<time.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;  // 指向底层的数组空间 int size;       // 存储的有效数据个数 int capacity;   // 数组空间的容量大小 
}HP;void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 堆的向上调整 
void AdjustUp(HPDataType* a, int child);// 堆的向下调整 
void AdjustDown(HPDataType* a, int n, int parent);// 交换两个元素 
void Swap(HPDataType* p1, HPDataType* p2);// 打印堆中的元素 
void HeapPrint(HP* php);// 初始化堆 
void HeapInit(HP* php);// 使用数组元素初始化堆 
void HeapInitArray(HP* php, int* a, int n);// 销毁堆 
void HeapDestroy(HP* php);// 堆的插入 
void HeapPush(HP* php, HPDataType x);// 堆的删除 
void HeapPop(HP* php);// 取堆顶元素 
HPDataType HeapTop(HP* php);// 堆的判空 
bool HeapEmpty(HP* php);// 获取堆的数据个数
int HeapSize(HP* php);

Heap.c

#include <Heap.h>void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 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){if (a[child] > a[parent])         // 不符合堆的性质，需要向上调整 {Swap(&a[child], &a[parent]);  // 交换双亲和孩子结点的值 // 孩子和双亲结点向上移动 child = parent;            parent = (parent - 1) / 2;}else                              // 符合堆的性质 {break;}}
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;  // 计算出左孩子结点的下标 while (child < n){// 找出小的那个孩子if (child + 1 < n && 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 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){perror("realloc fail");exit(-1);}php->a = tmp;                // 让堆数组指针指向新空间 php->capacity = newCapacity; // 更新容量大小 }php->a[php->size] = x;           // 在尾部插入数据 php->size++;                     // 有效数据++ AdjustUp(php->a, php->size - 1); // 向上调整，保持堆结构的特性 
}void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]); // 交换首尾元素 --php->size;                              // --sizeAdjustDown(php->a, php->size, 0);         // 向下调整 
}void HeapInitArray(HP* php, int* a, int n)
{assert(php);assert(a);php->a = (HPDataType*)malloc(sizeof(HPDataType)*n); // 动态申请数组空间 if (php->a == NULL)                                 // 判断空间的申请是否成功 {perror("malloc fail");exit(-1);}// size 和 capacity都置为待初始化数组的大小 php->size = n;php->capacity = n;// 把数据从待拷贝数组拷贝到堆数组中。 memcpy(php->a, a, sizeof(HPDataType) * n);// 向上调整建堆for (int i = 1; i < n; i++){AdjustUp(php->a, i);}
}HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0]; // 堆顶元素就是底层数组空间中的第一个元素 
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}// 获取堆的数据个数
int HeapSize(HP* php);
{assert(php);return php->size;	
}void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}


http://www.ppmy.cn/embedded/128260.html

相关文章

【私有云盘搭建】Portainer CE部署NextCloud，轻松实现公网访问

【私有云盘搭建】Portainer CE部署NextCloud，轻松实现公网访问

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
PCL 点云配准 KD-ICP算法（精配准）

PCL 点云配准 KD-ICP算法（精配准）

目录 一、概述 1.1原理 1.2实现步骤 1.3应用场景 二、代码实现 2.1关键函数 2.1.1 加载点云函数 2.1.2 构建KD树函数 2.1.3 KD-ICP配准函数 2.1.4 点云可视化函数 2.2完整代码 三、实现效果 PCL点云算法汇总及实战案例汇总的目录地址链接&#xff1a; PCL点云算法…
阅读更多...
【微服务】全面构建微服务监控体系：确保系统稳定与性能优化的关键

【微服务】全面构建微服务监控体系：确保系统稳定与性能优化的关键

目录 引言一、微服务监控概述1.1 微服务监控的定义1.2 微服务监控的重要性1.3 监控的核心目标1.4 微服务监控的关键指标1.5 监控的策略 二、微服务监控的架构2.1 监控架构图2.2 架构组件2.3 监控架构示意图 三、微服务监控的工具3.1 工具概述3.2 Prometheus3.3 Grafana3.4 ELK …
阅读更多...
解决：Ubuntu跑slam，遇到rviz闪退

解决：Ubuntu跑slam，遇到rviz闪退

在使用ros运行slam算法的时候&#xff0c;运行roslaunch aloam_velodyne aloam_velodyne_VLP_16.launch和rosbag play nsh_indoor_outdoor.bag中的某一条指令的时候&#xff0c;发现rviz启动后&#xff0c;里面没有内容&#xff0c;并且闪退。 我尝试关闭vmware中的3D加速&…
阅读更多...
使用docker搭建lnmp运行WordPress

使用docker搭建lnmp运行WordPress

一&#xff0c;部署目的 使用 Docker 技术在单机上部署 LNMP 服务&#xff08;Linux Nginx MySQL PHP&#xff09;。部署并运行 WordPress 网站平台。掌握 Docker 容器间的互联及数据卷共享。 二&#xff0c;部署环境 操作系统&#xff1a;CentOS 7Docker 版本&#xff1…
阅读更多...
Python3 标准库概览和例子

Python3 标准库概览和例子

一&#xff0c;Python3 标准库中的模块&#xff1a;1&#xff0c;os 模块&#xff1a;os 模块提供了许多与操作系统交互的函数&#xff0c;例如创建、移动和删除文件和目录&#xff0c;以及访问环境变量等。 2&#xff0c;sys 模块&#xff1a;sys 模块提供了与 Python 解释器…
阅读更多...
前端布局，y轴超出滚动、x轴超出展示方案

前端布局，y轴超出滚动、x轴超出展示方案

想要实现布局效果&#xff0c;红区高度固定可滑动可收起。红区引用绿区组件。 一般会想到如下方案&#xff0c;红区样式&#xff1a; width&#xff1a;200px; height: 100%; overflow-y: auto; overflow-x: visible; 但是效果并不好&#xff0c;绿区直接隐藏了 最终采用布局方…
阅读更多...
Jenkins整合Docker实现CICD自动化部署（若依项目）

Jenkins整合Docker实现CICD自动化部署（若依项目）

前期准备 提前准备好jenkins环境 并且jenkins能使用docker命令&#xff0c;并且已经配置好了jdk、node、maven环境&#xff0c;我之前写了安装jenkins的博客&#xff0c;里面讲得比较详细&#xff0c;推荐用我这种方式安装 docker安装jenkins&#xff0c;并配置jdk、node和m…
阅读更多...
最新文章

Copyright @ 2022~2023