2024年9月2日更新：深入解读什么是堆及堆的储存方法
更新时间：二〇二四年九月二日 上午九点二十八分零九秒 作者：敲上瘾
本文主要介绍C语言堆实现建堆算法与堆排序。文中借助示例代码介绍得极为详细。其对大家的学习或工作具备一定参考学习价值。有需要的朋友们，跟随小编一同学习吧
目录
一.什么是堆？1.堆
堆是完全二叉树，是特殊的完全二叉树。它要满足条件，若每个父节点都大于子节点，这叫大堆；若每个父节点都小于子节点，这叫小堆。对于兄弟节点间大小关系没要求（所以它不是有序的）。如下：
2.堆的储存
对于完全二叉树而言 存在一种更好的储存方式 那便是采用顺序表进行储存 相较于链式储存 使用顺序表储存有个很大的优点 即当知晓某一结点时 能够轻易算出它父结点的下标 也能轻易算出它子结点的下标 并且还能够随机访问
父子结点下标计算公式：
二.堆结构的创建1.头文件的声明：
Heap.h
#pragma #include#include #include #define HpDataType int typedef int HPDataType; typedef struct Heap { HPDataType* arr; int size; int cap; }Heap; 该函数参数为指向Heap结构体的指针php 堆的销毁，声明函数HeapDestory，参数为指向Heap结构体的指针hp 参数二为堆的数据类型 HPDataType 的值 x void HeapPop(Heap* hp);//堆的删除 HPDataType 取堆顶的数据函数 HeapTop，参数为 Heap* hp 整型 堆大小函数（堆指针）//获取堆中数据的个数 整型函数HeapEmpty，用于判断堆是否为空，参数为指向堆的指针hp 其功能是向上调整 定义一个名为AdjustDOWN的函数，该函数接收三个参数，分别是HpDataType类型指针arr、整型size和整型parent，其功能是向下调整 参数为HpDataType* a和HpDataType* b
其中堆的初始化、销毁、数据个数、判空，以及取堆顶数据的操作，和顺序表相同。这里重点学习堆的插入与删除。
2.向上调整
插入元素时直接往数组最后插入就行。不过插入后不一定是堆结构，所以需要调整。比如一个大堆：
向大堆中插入53
调整后：
代码示例：
第二个参数是整型变量child
{
计算父节点下标。通过(child - 1) / 2来得出，结果赋值给parent
当孩子大于0时//注意此处不能是父母大于0
{
if (arr[child] > arr[parent])
{
封装一个函数。该函数用于交换。交换的是数组中两个元素。这两个元素分别是arr[child]和arr[parent]
child = parent;//更新子节点
父节点等于（子节点减1）除以2
}
else
break;
}
}
如果是小堆只需要把if条件的大于号改为小于号
3.向下调整
要注意删除元素。我们删除的并非尾元素，那样做毫无意义。我们删除的是下标为0位置的元素。它是整个堆中最小或最大的元素。怎么删除呢？是直接将它删除然后让后面的元素覆盖上来吗？若如此操作 它便不再是堆 元素间关系会全然混乱 需从0开始创建堆 效率极低 我们能把首元素与尾元素互换 接着删除尾元素 虽说此操作后它可能不再是堆 但可将首元素向下调整 使其成为堆 比刚才方案效率高很多
比如我们删除大堆中的一个元素
调整过程：
调整后的结果：
代码示例：
第三个参数是整数parent
{
int child = parent * 2 + 1;
while (child < size)
{
if ((child+1) arr[parent])
{
交换数组中父节点位置的元素和子节点位置的元素
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
还需要改变父子节点的大小关系
4.源码：
定义 _CRT_SECURE_NO_WARNINGS 为 1
#include"Heap.h"
void HeapInit(Heap* ps)//初始化
{
assert(ps);
ps->arr = NULL;
ps->cap = ps->size = 0;
}
void HeapDestory(Heap* hp) //进行堆的销毁操作
{
assert(hp);
free(hp->arr);
hp->cap = hp->size = 0;
}
函数功能是交换元素
{
HpDataType c = *a;
*a = *b;
*b = c;
}
使向上调整无效（Hp数据类型指针*数组，整数子节点）//向下调整
{
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 size, int parent)//向上调整
{
int child = parent * 2 + 1;
while (child < size)
{
if (arr[child] > arr[child + 1])
child++;
if ((child+1)size == ps->cap)
{
如果ps的cap值等于0 那么pnc赋值为4 否则pnc赋值为ps的cap值乘以2
HpDataType指针pnew指向通过realloc函数重新分配内存后的地址，该内存大小为HPDataType类型大小乘以pnc，原内存地址由ps->arr指向
assert(pnew);
ps->arr = pnew;
ps->cap = pnc;
}
ps->arr[ps->size] = x;
ps->size++;
调整向上（ps指向的数组，ps的大小减1）
}
void HeapPop(Heap* hp)//删除元素
{
assert(hp);
assert(hp->size);
if (hp->size == 1)
{
hp->size--;
return;
}
把hp->arr[0]与hp->arr[hp->size - 1]进行交换处理
hp->size--;
对hp指向的数组进行向下调整，调整范围是hp的大小，起始位置为0
}
HPDataType HeapTop函数用于取堆顶元素，该函数的参数为Heap* hp类型的指针，函数名为HeapTop
{
assert(hp);
assert(hp->size);
return hp->arr[0];
}
函数返回值为整型
{
assert(hp);
return hp->size;
}
函数返回值为整型
{
assert(hp);
return hp->size == 0;
}
三.建堆算法
学习建堆算法时以对数组建堆为例。就是将数组数据间的关系做成堆结构。一般有两种方法。分别是向上调整建堆和向下调整建堆。具体做法如下。
1.向上建堆法
向上建堆法是通过向上调整来建堆。拿到一个数组后，将数组首元素当作堆。把第二个元素当作新元素插入堆中。接着通过向上调整构成新的堆。依此类推，遍历完数组后一个堆就建成了。其时间复杂度为O(N*logN)
代码示例：
#include#include"Heap.h" int main() { 其值为数组arr的大小除以整型的大小 for (int i = 0; i < size; i++) AdjustUP(arr, i);//该函数在上文已给出，这里不再展示 printf("建大堆后：\n"); for (int i = 0; i < size; i++) printf("%d ", arr[i]); return 0; }
不过该方法与向下调整建堆相比，效率较低。我们来看看向下调整建堆法。
2.向下建堆法
向下建堆法是通过向下调整来建堆。要注意不能从首元素开始调整。因为刚开始时它不满足左右子树都是堆结构。所以不能直接从第一个元素开始向下调整。既然要使左右子树都成为堆，那我们可以考虑从最后一个元素着手调整。不过最后一层下面已无元素，它已然是堆，无需调整。如此，我们从倒数第二层开始调整。所以，我们先来算一算倒数第二层最后一个父节点的下标：
(size-1-1)/2
第一个size - 1获取二叉树最后一个元素的下标。将该下标减一。用减一之后的结果除以二。得到其父节点的下标。
代码示例：
#include#include"Heap.h" int main() { int arr[] = { 1,9,3,7,6,4,2,10,8,5 }; int size = sizeof(arr) / sizeof(int); 每次循环 i 自减 1 调用AdjustDOWN函数，参数为arr、size、i 该函数在上文已给出 这里不再展示 printf("建大堆后：\n"); for (int i = 0; i < size; i++) printf("%d ", arr[i]); return 0; }
它的时间复杂度为O(N)证明如下：
其中Sn为总的调整次数.
四.堆排序
将一个数组建堆。利用堆的性质对数组排序，让效率更高。这便是堆排序。例如要对一个数组做堆排序。首要问题是建大堆还是小堆。以及如何利用堆为数组排序。
要进行升序，就得建大堆。要是建的是小堆，堆顶即首元素就是最小元素，无需变动。处理第二个元素时会发现，它不一定是第二小的元素，只能从第二个元素开始重新建一个小堆。如此，每排一个元素都要重新建一个小堆，效率就会变得很低。
若按升序构建大堆，那么第一个元素即为最大元素。我们能够让它与最后一个元素进行互换。接着把堆的元素个数减一，这意味着将最后一个元素视为在堆外。最后对堆顶元素进行向下调整，不断重复此操作，直至堆的元素个数变为零。如此一来，一个数组便按升序排列好了。
降序需要建小堆，原理和排升序相同这里就不在赘述。
代码示例：
#include#include"Heap.h" int main() { int arr[] = { 1,9,3,7,6,4,2,10,8,5 }; int size = sizeof(arr) / sizeof(int); for (int i = (size - 1 - 1) / 2; i >= 0; i--) AdjustDOWN(arr, size,i); printf("建大堆后：\n"); for (int i = 0; i < size; i++) printf("%d ", arr[i]); while (size) { Swap(&arr[0], &arr[size - 1]);//交换元素 size--; AdjustDOWN(arr, size, 0); } printf("\n排序后；\n"); for (int i = 0; i < sizeof(arr) / sizeof(int); i++) printf("%d ", arr[i]); return 0; }
五.在文件中Top出最小的K个数
使用堆结构有个好处。无需排序就能高效找出最小的前n个元素或最大的前n个元素。现在我们利用堆尝试找出文件中最小的K个数。一种比较低效的方法是。取出文件中涉及的所有数据。将其建成一个小堆。然后Pop出前k次。得到最小的k个数。但是倘若这个数据极大呢。比如说存在上亿个数据。如此便会耗费极大的内存空间。
有一种非常好的方法。就是只取出文件的前K个数来建成一个大堆。这个堆只存储K个元素。堆顶就是这个堆的最大元素。接着继续遍历文件。每遍历一个元素。都与堆顶元素作比较。如果比堆顶元素小。就更新堆顶元素。把小的那个变为堆顶元素。然后进行向下调整。直到遍历完整个文件。此时堆中的元素就是文件中最小的K个元素。这种方法在时间复杂度方面和上一种方法相近。然而它极大地节省了空间。
代码示例：
#include#include"Heap.h" void CreateNDate() { //造数据，写入文件中 int n = 10000; 使用当前时间的无符号整型值作为种子来初始化随机数生成器 该指针指向的内容为"data.txt" FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; ++i) { int x = rand() % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void PrintTopK(int k) { int* arr = (int*)malloc(sizeof(int) * k); assert(arr); FILE* fop = fopen("data.txt", "r"); if (!fop) { perror("fopen error"); return; } for (int i = 0; i < k; i++)//先取出k个建大堆 fscanf(fop, "%d", &arr[i]); for (int i = (k - 1 - 1) / 2; i >= 0; i--) AdjustDOWN(arr, k, i); int x = 0; 当使用fscanf函数从fop中读取一个整数到x，且读取结果不等于文件结束标志时 { if (arr[0] > x) { arr[0] = x; AdjustDOWN(arr, k, 0); } } for (int i = 0; i < k; i++)//输出堆中元素 printf("%d ", arr[i]); } int main() { CreateNDate(); int k = 0; scanf("%d", &k); PrintTopK(k); return 0; }
关于C语言堆实现建堆算法和堆排序的文章，到此介绍完毕。更多相关C语言堆内容，可搜索脚本之家以前的文章，或继续浏览下面的相关文章。希望大家以后多多支持脚本之家！
phper