一篇解建堆，堆的实现，堆排序，TopK问题C语言《数据结构和算法》

原来45

2024-04-24 帮助1人

1. 堆的概念及结构 🚀

hello✨，大家好呀，这里是原来💖 💛💙随着文章篇幅越来越多可能有很多小伙伴们找不到自己想要看的文章🎁 🎁 🎁C语言的入门篇进阶篇和深剖篇都整理在这里了哈。然后这里是个人主页，比点头像更好找文章哈。🎈 🎈🎈

期待hxd的支持哈🎉 🎉 🎉

这里附带作者qq：2777137742

vx：q2777137742

因为私信消息很多不容易看见哈

最后是打鸡血环节：改变的确很难，但结果值得冒险，拿出点勇气来。路还很长，现在才刚开始而已。过去无可挽回，未来可以改变。🚀 🚀 🚀

1. 堆的概念及结构 🚀

还有堆的左右子树都是大堆或者小堆，堆顶是最大值或者最小值。

2. 堆的实现 🚀

在实现堆有两个比较重要的事情就是理解向上调整算法和向下调整算法。

堆的向上调整算法：是为了在插入数据的时候使原来的结构不变，还是一个堆。

堆的向下调整算法：1.是为了建堆。或者给你一个数组这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，我们要通过算法，把它构建成一个堆。2.删除堆数据的时候要用向下调整算法。

2.1. 堆向下调整算法 🚀

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};

2.2. 堆的创建 🚀

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过向下调整算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};

2.3. 建堆时间复杂度 🚀

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果) ：

2.4. 堆的插入 🚀

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。（数据从下往上调，所以是向上调整算法）

2.5. 堆的删除 🚀

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

3. 堆的应用 🚀

3.1 堆排序 🚀

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

升序：建大堆

降序：建小堆

2. 利用堆删除思想来进行排序（时间复杂度：NLogN 和 qsort一个等级哈）

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

3.2 TOP-K问题 🚀

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。

比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100的活跃玩家等。

对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子（指时间短暂或动作迅速）（指时间短暂或动作迅速）全部加载到内存中) 。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前 K 个元素来建堆

前 k 个最大的元素，则建小堆

前 k 个最小的元素，则建大堆

2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素

注意

上面说的所有，如果不太理解，我们直接看下面的代码，作者是认为一个程序员代码可能给你的理解要比大白话要更直接哈。

4. 源代码 🚀

这里作者是建的小堆，如果要建大堆就改作者在代码里面声明的地方，就把三个小于改成大于就可以了哈。

源代码里面解决了：建堆（给一个数组建堆），堆的各项操作，堆排序，TopK问题。

PS:代码里面有详细的解释哈。

main函数里面test1里面是建堆的各项操作的测试及堆排序的测试。

test2里面是给一个数组然后建堆的测试哈。

4.1. Heap.h 🚀

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<errno.h>
#include<stdbool.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
size_t size;
size_t capacity;
}Heap;
//初始化
void HeapInit(Heap* php);
//打印
void HeapPrint(Heap* php);
// 堆的构建
void HeapCreate(Heap* php, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
size_t HeapSize(Heap* php);
// 堆的判空
bool HeapEmpty(Heap* php);
//堆排序 NLogN
void HeapSort(int* a, size_t size);
// TopK问题：找出N个数里面最大/最小的前K个问题。
// 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题，
// 需要注意：
// 找最大的前K个，建立K个数的小堆
// 找最小的前K个，建立K个数的大堆
void PrintTopK(int* a, int n, int k);
void TestTopk();

4.2. Heap.c 🚀

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void AdjustDown(HPDataType* a, size_t sz, size_t root);
堆的构建
//void HeapCreate(Heap* php, HPDataType* a, int n)
//{
// assert(php);
// HPDataType* new = (HPDataType*)malloc(sizeof(HPDataType) * n);
// if (new == NULL)
// {
// perror("HeapCreate failed!\n");
// exit(-1);
// }
// php->a = new;
// php->capacity=n;
// php->size = 0;
// int curpos = php->size / 2 - 1;
// while (curpos >= 0)
// {
// AdjustDown(php->a, 7,curpos);
// curpos--;
// }
//}
//给数组建堆
void HeapCreate(Heap* php, int arr[], int n)
{
php->a = (int*)malloc(sizeof(HPDataType) * n);
assert(php->a != NULL);
php->capacity = n;
php->size = n;
//先把数据进堆
for (int i = 0; i < n; i)
php->a[i] = arr[i];
//先找到最后一个分支的第一个非叶子节点
int curpos = php->size / 2 - 1;
while (curpos >= 0)
{
AdjustDown(php->a, 7,curpos);
curpos--;
}
}
//初始化
void HeapInit(Heap* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
//打印
void HeapPrint(Heap* php)
{
assert(php);
assert(php->size > 0);
for (size_t i = 0; i < php->size; i )
{
printf("%d ", php->a[i]);
}
printf("\n");
}
// 堆的销毁
void HeapDestory(Heap* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
free(php->a);
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//小堆为例大堆换符合就可以了
//向上调整算法
void AdjustUP(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
while (child>0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
}
else
{
break;
}
child = parent;
parent= (child - 1) / 2;
}
}
//向下调整算法
void AdjustDown(HPDataType* a, size_t sz, size_t root)
{
//先找左右小的孩子
//再和root的比比root小就交换
//root等于那个要交换的孩子孩子再选然后迭代
//改为这个可能更好看一点
//size_t parent = root;
//这里默认左孩子
//size_t child = parent * 2 1;
//这里默认左孩子
size_t child = root * 2 1;
//sz的作用就是确保左右还在在数组内
while (child<sz)
{
//小心右孩子不存在
//找左右孩子小的
//还有注意要把比较左右孩子放进循环，因为每次都要比较
if (child 1<sz && a[child 1] < a[child])
{
child = child 1;
}
if (a[child] < a[root])
{
Swap(&a[child], &a[root]);
root = child;
child = root * 2 1;
}
else
{
break;
}
}
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
if (php->capacity == php->size)
{
size_t newcapacity = php->capacity == 0 ? 4 : php->capacity*2;
HPDataType* new = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (new == NULL)
{
printf("%s", strerror(errno));
exit(-1);
}
php->a = new;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size ;
//上面是插入数据
//下面是向上调整算法使插入数据后还是一个小堆
AdjustUP(php->a,php->size-1);
}
// 堆的删除
void HeapPop(Heap* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
//传参注意一下
AdjustDown(php->a,php->size,0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{
assert(php);
assert(php->size > 0);
HPDataType top = php->a[0];
return top;
}
// 堆的判空
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}
// 堆的数据个数
size_t HeapSize(Heap* php)
{
assert(php);
return php->size;
}
//现在默认小堆，想变为大堆就把上面的向上向下调整算法改一下判断就可以了(3个)
//堆排序时间复杂度: NLogN
//为什么是NLogN:因为每次插入数据都是一层只插入一个数据(假设是满二叉树,总
// 节点个数就是2^k-1:(2^(k-1)*2-1/(2-1))=N)，k=Log2(k 1),即LogN)
// 又因为有N个数要排
//所以就是N*LogN
void HeapSort(int* a, size_t size)
{
assert(a);
Heap hp;
HeapInit(&hp);
size_t i = 0;
for (i = 0; i < size; i )
{
HeapPush(&hp, a[i]);
}
while (!HeapEmpty(&hp))
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
HeapDestory(&hp);
}
// TopK问题：找出N个数里面最大/最小的前K个问题。
// 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，
// 全国排名前10的李白。等等问题都是Topk问题，
// 需要注意：
// 找最大的前K个，建立K个数的小堆
// 找最小的前K个，建立K个数的大堆
void PrintTopK(int* a, int n, int k)
{
assert(a);
assert(k < n);
Heap hp;
HeapInit(&hp);
int i = 0;
for (i = 0; i < n; i )
{
HeapPush(&hp, a[i]);
}
while (k--)
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
}
void TestTopk()
{
//int arr[] = { 15,18,19,25,28,34,65,49,27,37 };
//int sz = sizeof(arr) / sizeof(arr[0]);
//int k = 5;
//PrintTopK(arr, sz, k);
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
srand(time(0));
for (size_t i = 0; i < n; i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 1;
a[1231] = 1000000 2;
a[531] = 1000000 3;
a[5121] = 1000000 4;
a[115] = 1000000 5;
a[2335] = 1000000 6;
a[9999] = 1000000 7;
a[76] = 1000000 8;
a[423] = 1000000 9;
a[3144] = 1000000 10;
PrintTopK(a, n, 10);
}

4.3. test.c 🚀

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void test1()
{
//Heap hp;
//HeapInit(&hp);
HeapCreate(&hp, arr, 10);
//HeapPush(&hp, 1);
//HeapPrint(&hp);
//HeapPush(&hp, 5);
//HeapPrint(&hp);
//HeapPush(&hp, 0);
//HeapPrint(&hp);
//HeapPush(&hp, 8);
//HeapPrint(&hp);
//HeapPush(&hp, 3);
//HeapPrint(&hp);
//HeapPush(&hp, 9);
//HeapPrint(&hp);
//HeapPush(&hp, 17);
//HeapPrint(&hp);
//HeapPush(&hp, 13);
//HeapPush(&hp, 15);
//HeapPush(&hp, 20);
//HeapPrint(&hp);
//printf("size=%d \n", HeapSize(&hp));
//while (!HeapEmpty(&hp))
//{
// printf("%d ", HeapTop(&hp));
// HeapPop(&hp);
//}
//HeapDestory(&hp);
/// //
//升序
int arr[] = { 15,18,19,25,28,34,65,49,27,37 };
size_t sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
//
TestTopk();
}
void test2()
{
Heap hp;
HeapInit(&hp);
int arr[] = { 3,7,5,2,9,10,15 };
HeapCreate(&hp, arr, 7);
for (int i = 0; i < 7; i )
{
printf("%d ", hp.a[i]);
}
}
int main()
{
test1();
//test2();
return 0;
}

最后的最后，创作不易，希望读者三连支持💖

赠人玫瑰，手有余香💖

这篇好文章是转载于：学新通技术网

一篇解建堆，堆的实现，堆排序，TopK问题C语言《数据结构和算法》

1. 堆的概念及结构 🚀

2. 堆的实现 🚀

2.1. 堆向下调整算法 🚀

2.2. 堆的创建 🚀

2.4. 堆的插入 🚀

2.5. 堆的删除 🚀

3. 堆的应用 🚀

3.1 堆排序 🚀

3.2 TOP-K问题 🚀

注意

4. 源代码 🚀

4.1. Heap.h 🚀

4.2. Heap.c 🚀

4.3. test.c 🚀

photoshop保存的图片太大微信发不了怎么办

Android 11 保存文件到外部存储，并分享文件

《学习通》视频自动暂停处理方法

word里面弄一个表格后上面的标题会跑到下面怎么办

photoshop扩展功能面板显示灰色怎么办

微信公众号没有声音提示怎么办

excel下划线不显示怎么办

excel打印预览压线压字怎么办

怎样阻止微信小程序自动打开

TikTok加速器哪个好免费的TK加速器推荐