👀樊梓慕:个人主页
🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》
🌝每一个不曾起舞的日子,都是对生命的辜负
目录
前言
1.堆的概念和结构
2.堆的实现
2.1向上调整算法
2.2向下调整算法
2.3堆的创建
2.4建堆时间复杂度
2.5堆的插入
2.6堆的删除
2.7堆的代码实现
3.堆的应用
3.1堆排序
3.2TopK问题
前言
本篇文章博主主要围绕堆这一数据结构展开,内容包括两种建堆方式,两种建堆方式的时间复杂度分析,最后引入堆的应用:堆排序和TopK问题,希望大家多多点赞收藏支持🔥
欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。
=========================================================================文章来源地址https://www.toymoban.com/news/detail-725181.html
GITEE相关代码:🌟fanfei_c的仓库🌟
=========================================================================
1.堆的概念和结构
堆的逻辑结构是完全二叉树。
逻辑结构的视角观察:
在大根堆中,双亲节点大于孩子节点;
在小根堆中,双亲节点小于孩子节点。
堆的存储结构是一维数组。
存储结构的视角观察(设数组K):
在小根堆中:K[i]<=K[2*i+1] && K[i]<=K[2*i+2];
在大根堆中:K[i]>=K[2*i+1] && K[i]>=K[2*i+2];
2.堆的实现
2.1向上调整算法
向上调整算法的前提是祖先是堆。
以小堆为例:
1.给定向上调整的起点(孩子节点下标),根据起点下标计算双亲节点下标。
孩子节点与双亲结点间的下标关系:
child=parent*2+1 || child=parent*2+2;
parent=(child-1)/2;
2.比较孩子节点与双亲节点数值大小,若孩子节点小于双亲节点,则交换两者,并将孩子节点的下标更新为之前的双亲节点下标,根据最新的孩子节点下标重新计算双亲节点下标,重复这一过程直到孩子节点为根节点。
代码实现:
//向上调整
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;
}
}
}
2.2向下调整算法
向下调整算法的前提是左右子树是堆。
以小堆为例:
1.给定向下调整的起点(双亲节点下标)和节点总数,根据起点下标计算孩子节点下标。
注意:向下调整时,若有两个孩子节点,则需要确保调整的是较小的孩子节点。
2.比较孩子节点与双亲节点数值大小,若孩子节点小于双亲节点,则交换两者,并将双亲节点的下标更新为之前的孩子节点下标,根据最新的双亲节点下标重新计算孩子节点下标,重复这一过程直到孩子节点超出节点总数。
代码实现:
//向下调整
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 = child + 1;
}
if (a[child] < a[parent])//建小堆
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
2.3堆的创建
堆的创建既可以使用向上调整算法,也可以使用向下调整算法。
1.向上调整算法建堆
由于向上调整算法的前提是祖先是堆,所以我们需要从第二个节点开始向上调整(即根节点的下一个)。
代码实现:
for(int i = 1; i < n; i++)
{
Adjustup(a,i);
}
2.向下调整算法建堆
由于向下调整算法的前提是左右子树是堆,所以我们需要从倒数第一个非叶子节点向下调整。
已知节点总数为n,那么倒数第一个节点的下标即为n-1,该节点的双亲节点下标即为(n-1-1)/2,该双亲节点就是倒数第一个非叶子节点(因为堆是完全二叉树)。
代码实现:
for (int i = (n - 2) / 2; i >= 0; i--)
{
Adjustdown(a,n,i);
}
2.4建堆时间复杂度
假设树的高度为h。
1.向上调整建堆时间复杂度
则需要移动节点总的移动步数为:
即向上调整建堆的时间复杂度为O(N*log₂N)。
2.向下调整建堆时间复杂度
则需要移动节点总的移动步数为:
即向下调整建堆的时间复杂度为O(N)。
2.5堆的插入
首先尾插到该数组,再向上调整即可。
2.6堆的删除
删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。
2.7堆的代码实现
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
assert(a);
hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
if (hp->a == NULL)
{
perror("malloc fail");
exit(-1);
}
hp->capacity = hp->size = n;
memcpy(hp->a, a, sizeof(HPDataType) * n);
for (int i = 1; i < n; i++)
{
Adjustup(hp->a, i);
}
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->capacity = hp->size = 0;
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
assert(hp->a);
//1.检查容量
if (hp->size == hp->capacity)
{
int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) *newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
Adjustup(hp->a, hp->size-1);
}
// 堆的删除
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
Swap(&hp->a[0], &hp->a[hp->size - 1]);
--hp->size;
Adjustdown(hp->a, hp->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->a);
return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
3.堆的应用
3.1堆排序
方法1:
首先,我们当然可以利用已经堆这一数据结构进行输出有序的数据。
以升序为例:
首先构建小堆,然后输出堆顶元素,再Pop,再向下调整,循环执行此步骤直到堆空。
代码实现:
void HeapSort(int* a, int n)
{
HP hp;
HeapInit(&hp);
for (int i = 0; i < n; i++)
{
HeapPush(&hp, a[i]);
}
int i = 0;
while (!HeapEmpty(&hp))
{
//printf("%d ", HeapTop(&hp));
a[i++] = HeapTop(&hp);
HeapPop(&hp);
}
HeapDestroy(&hp);
}
但这样有很明显的缺点:
1.需要堆这样一个数据结构,构建麻烦;
2.空间复杂度的消耗。
方法2:
以升序为例:
首先构建大堆(推荐使用向下调整),此时堆顶元素一定为最大值,然后将堆顶元素与最后一个节点交换,此时最大值就放到了整个数组的最后面,然后除了最后一个值以外,其他的数据再向下调整,调整完成后堆顶元素为次大值,再与数组倒数第二个位置的值交换,这样依此往复就得到了升序数组。
注意:
升序建大堆,降序建小堆。
代码实现:
void HeapSort(int* a, int n)
{
// 向上调整建堆 (大堆)or (小堆)
// 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;
}
}
3.2TopK问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
最佳的方式就是用堆来解决,基本思路如下:
1.用数据集合中前K个元素来建堆
- 前k个最大的元素,则建小堆
- 前k个最小的元素,则建大堆
2.用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
首先可以写一段生成随机数字的程序,并将这些数字写入到文件中。
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);
}
根据上面分析的思路完成代码。
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");
fclose(fout);
}
堆处理大量数据的速度非常快,我们都知道对数的特性,所以堆处理大量数据的能力非常强。在遇到TopK问题或者大量数据排序时,可以考虑使用堆排序。
=========================================================================
如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容
🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏+关注 ~🌟文章来源:https://www.toymoban.com/news/detail-725181.html
=========================================================================
到了这里,关于【数据结构】堆排序与TopK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!