数据结构：堆的保姆级教学指南

ops/2024/9/23 4:20:39/

✨✨小新课堂开课了，欢迎欢迎~✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法

小新的主页：编程版小新-CSDN博客

1.堆的概念

堆是一种特殊的树结构，通常用于高效地实现优先遍历。堆可以分为大根堆和小根堆。

堆的性质：
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。

大根堆：任意节点的值大于其子节点的值

小根堆：任意节点的值小于其子节点的值

2.堆的实现 

堆通常用数组来实现，通过一些特定的操作可以高效地完成其相关功能的实现。

通过下标我们也能找到一个节点其对应的父节点和子节点。

父节点存在的情况下，parent = (child-1)/2;

子节点存在的情况下，leftchild = 2*parent+1；rightchild = 2*parent+2;

这里的parent和child指的都是下标。

3.堆的功能

堆的初始化

判断堆是否为空

堆的插入

堆的删除

获取堆顶元素

返回堆的大小

输出堆

建堆

销毁堆

4.堆的声明

堆通常是用数组来实现的。

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

5.堆的功能实现

5.1堆的初始化

//初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;//数据个数php->capacity = 0;//容量大小
}

5.2判断堆是否为空

//检查是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

5.3堆的插入

我们这里以建小堆为例，若想建大堆只需更改判断a[child]与a[parent]的大小关系即可。

//交换位置
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 = (child - 1) / 2;}else{break;}}
}//入堆
void HPPush(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,newcapacity*sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->capacity = newcapacity;php->a = tmp;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

这是一个比较详细的调整过程，根据代码进行一步步比对操作可以更容易理解。 

 

5.4堆的删除

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = 2 * parent + 1;while (child<n){//找到那个较小的孩子（左孩子/右孩子）if (child + 1 < n && a[child] > a[child + 1]){child++;}if(a[parent]>a[child]){SWap(&a[parent], &a[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}//出堆
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));SWap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

 向下调整是比较不好理解的，下面是详细的思路。

 

5.5获取堆顶元素

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

5.6返回堆的大小

//获取堆的元素个数
int HPSize(HP* php)
{assert(php);return php->size;
}

5.7输出堆

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

5.8建堆

//向上调整建堆O(N*logN)
void HPCreatUp(HP* php,HPDataType* a,int n)
{assert(php && a);for (int i = 0; i < n; i++){AdjustUp(a, i);}
}//向下调整建堆1 O(N)
void HPCreatDown1(HP* php, HPDataType* a, int n)
{assert(php && a);for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n是数据个数，n-1是最后一个数据的下标，(n-1-1)/2是求双亲的下标{AdjustDown(a, n,i);}
}//向下调整建堆2 O(N*logN)
void HPCreatDown2(HP* php, HPDataType* a, int n)
{int end = n - 1;while (end > 0){SWap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

补充：

向上调整建堆算法的时间复杂度分析

向下调整建堆算法的时间复杂度分析

 

5.9销毁堆

//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

5.10完整代码

Heap.h:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;}HP;
//初始化
void HPInit(HP* php);//检查是否为空
bool HPEmpty(HP* php);//交换位置
void SWap(HPDataType* p1, HPDataType* p2);//向上调整
void AdjustUp(HPDataType* a, int child);//入堆
void HPPush(HP* php, HPDataType x);//向下调整
void AdjustDown(HPDataType* a, int n, int parent);//出堆
void HPPop(HP* php);//取堆顶数据
HPDataType HPTop(HP* php);//获取堆的元素个数
int HPSize(HP* php);//向上调整建堆O(N*logN)
void HPCreatUp(HP* php, HPDataType* a, int n);//向下调整建堆1 O(N)
void HPCreatDown1(HP* php, HPDataType* a, int n);//向下调整建堆2 O(N*logN)
void HPCreatDown2(HP* php, HPDataType* a, int n);//打印堆
void HPDisplay(HP* php);//销毁堆
void HPDestroy(HP* php);

Heap.c:

#include"Heap.h"//初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}//检查是否为空
bool HPEmpty(HP* php)
{assert(php);return 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){if (a[child] < a[parent]){SWap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆
void HPPush(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,newcapacity*sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->capacity = newcapacity;php->a = tmp;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = 2 * parent + 1;while (child<n){//找到那个较小的孩子（左孩子/右孩子）if (child + 1 < n && a[child] > a[child + 1]){child++;}if(a[parent]>a[child]){SWap(&a[parent], &a[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}//出堆
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));SWap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}//取堆顶数据
HPDataType HPTop(HP* php)
{assert(php);assert(!HPEmpty(php));return php->a[0];
}//获取堆的元素个数
int HPSize(HP* php)
{assert(php);return php->size;
}//打印堆
void HPDisplay(HP* php)
{for (int i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}//向上调整建堆O(N*logN)
void HPCreatUp(HP* php,HPDataType* a,int n)
{assert(php && a);for (int i = 0; i < n; i++){AdjustUp(a, i);}
}//向下调整建堆1 O(N)
void HPCreatDown1(HP* php, HPDataType* a, int n)
{assert(php && a);for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n是数据个数，n-1是最后一个数据的下标，(n-1-1)/2是求双亲的下标{AdjustDown(a, n,i);}
}//向下调整建堆2 O(N*logN)
void HPCreatDown2(HP* php, HPDataType* a, int n)
{int end = n - 1;while (end > 0){SWap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

6.堆的实际运用

6.1堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
升序：建大堆
降序：建小堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

//交换位置
void SWap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = 2 * parent + 1;while (child<n){//找到那个较小的孩子（左孩子/右孩子）if (child + 1 < n && a[child] > a[child + 1]){child++;}if(a[parent]>a[child]){SWap(&a[parent], &a[child]);parent = child;child = 2 * parent + 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;}
}//打印堆
void HPDisplay(HP* php)
{for (int i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}

6.2TopK问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。


对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.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 AdjustDown(HPDataType* a, int n, int parent)
{int child = 2 * parent + 1;while (child < n){//找到那个较小的孩子（左孩子/右孩子）if (child + 1 < n && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){SWap(&a[parent], &a[child]);parent = child;child = 2 * parent + 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;}
}//打印堆
void HPDisplay(HP* php)
{for (int i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}void CreatData()
{// 造数据int n = 100000;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);
}void TopK()
{int k;printf("请输入k>:");scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}// 读取文件中前k个数for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}// 11:51继续// 建K个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}// 读取剩下的N-K个数int x = 0;while (fscanf(fout, "%d", &x) > 0){if (x > kminheap[0]){kminheap[0] = x;AdjustDown(kminheap, k, 0);}}printf("最大前%d个数：", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");
}
//TopK问题
int main()
{//CreatData();TopK();return 0;
}


http://www.ppmy.cn/ops/45792.html

相关文章

容器多机部署eureka及相关集群服务出现 Request execution failed with message: AuthScheme is null

容器多机部署eureka及相关集群服务出现 Request execution failed with message: AuthScheme is null

预期部署方案&#xff1a;两个eureka三个相关应用 注册时应用出现&#xff1a;Request execution failed with message: Cannot invoke “Object.getClass()” because “authScheme” is null&#xff0c;一开始认为未正确传递eureka配置的账户密码&#xff0c;例&#xff1a;…
阅读更多...
linux实用命令

linux实用命令

1、find 1.1 查找当前目录下含有BMSJ的文件名的文件 find . -name “*BMSJ*” 2、 sftp 2.1 远程连接 sftp usernameip username:用户名 ip&#xff1a;远程机 2.2 从远程下载 get HB*202405* /home/ftp 将远程的符合HB*202405*的文件从远程下载到本地服务器的 /home/ftp目录…
阅读更多...
Elasticsearch (ES) (上万字）详细学习总结

Elasticsearch (ES) (上万字）详细学习总结

一、认识ES 二、ES相关安装和部署(elasticsearch 、kbana、ik) 这部分的内容可以查看我之前写的Docker常用部署这篇文章 三、Mapping映射 3.1 Mapping映射属性 3.2 索引库操作 3.2.1 遵循Restful规范说明 3.2.2 具体使用方式说明 3.2.3增删改查示例 #创建 PUT /heima {&q…
阅读更多...
不借助三方平台自主搭建量化回测系统 ——以海龟交易策略为例

不借助三方平台自主搭建量化回测系统 ——以海龟交易策略为例

数量技术宅团队在CSDN学院推出了量化投资系列课程 欢迎有兴趣系统学习量化投资的同学&#xff0c;点击下方链接报名&#xff1a; 量化投资速成营&#xff08;入门课程&#xff09; Python股票量化投资 Python期货量化投资 Python数字货币量化投资 C语言CTP期货交易系统开…
阅读更多...
云动态摘要 2024-05-31

云动态摘要 2024-05-31

给您带来云厂商的最新动态&#xff0c;最新产品资讯和最新优惠更新。 最新优惠与活动 [1.5折起]年中盛惠--AI分会场 腾讯云 2024-05-30 人脸核身、语音识别、文字识别、数智人、腾讯混元等热门AI产品特惠&#xff0c;1.5折起 云服务器ECS试用产品续用 阿里云 2024-04-14 云…
阅读更多...
MySQL统计字符长度：CHAR_LENGTH(str)

MySQL统计字符长度：CHAR_LENGTH(str)

对于SQL表&#xff0c;用于计算字符串中字符数的最佳函数是 CHAR_LENGTH(str)&#xff0c;它返回字符串 str 的长度。 另一个常用的函数 LENGTH(str) 在这个问题中也适用&#xff0c;因为列 content 只包含英文字符&#xff0c;没有特殊字符。否则&#xff0c;LENGTH() 可能会返…
阅读更多...
身份认证与口令攻击

身份认证与口令攻击

身份认证与口令攻击 身份认证身份认证的五种方式口令认证静态口令动态口令(一次性口令)动态口令分类 密码学认证一次性口令认证S/KEY协议改进的S/KEY协议 其于共享密钥的认证 口令行为规律和口令猜测口令规律口令猜测 口令破解操作系统口令破解Windows密码存储机制Windows密码破…
阅读更多...
C语言--toupper/tolower/isupper/islower函数介绍

C语言--toupper/tolower/isupper/islower函数介绍

介绍 toupper&#xff08;&#xff09; 是一个用于将字符转换为大写的 C/C 函数&#xff0c;它位于 头文件中。使用 toupper 函数很简单&#xff0c;只需要将要转换的字符作为参数传递给它即可。 同理&#xff1a;tolower&#xff08;&#xff09;是将一个字符转换为小写的函数…
阅读更多...
最新文章

Copyright @ 2022~2023