网站开发流程步骤,经典网站源码,工程预算培训,企业网站的制作方式个人主页
代码仓库
C语言专栏
初阶数据结构专栏
Linux专栏
接上篇二叉树和堆的引入 目录
前言
建堆
插入数据向上调整算法建堆
移动数据向上调整算法建堆
无序数组从H-1层向上移动的向下调整算法建堆
堆排序
TOP-K问题 前言 上篇文章详细讲解了堆#xff0c;…
个人主页
代码仓库
C语言专栏
初阶数据结构专栏
Linux专栏 接上篇二叉树和堆的引入 目录
前言
建堆
插入数据向上调整算法建堆
移动数据向上调整算法建堆
无序数组从H-1层向上移动的向下调整算法建堆
堆排序
TOP-K问题 前言 上篇文章详细讲解了堆最后在执行完整代码后我们发现在删除堆中的数据时可以实现排序当然这不是偶然一切都是有迹可循的今天就来讲解下用堆来实现排序以及使用堆排序解决TopK问题。 建堆
插入数据向上调整算法建堆
上篇文章中我们就实现了这个步骤在主函数中创建了个数组然后将数组中的每个数据使用插入函数和向上调整算法函数依次插入动态开辟的空间中每插入一个数据作为孩子和父亲相比较根据大小交换位置最终实现大/小堆。
插入函数
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, sizeof(HPDatatype)*newcapacity);if (tmp NULL){perror(realloc failed);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;HPadjustUp(php-a, php-size-1);
}
进入函数首先判断空间大小是否足够 不够的话使用realloc库函数开辟空间开辟不成功直接退出开辟成功的话赋值和修改size和容量。
向上调整函数和交换函数
void HPadjustUp(HPDatatype* a, int child)
{//找到父亲int parent (child - 1) / 2;//根为0 当和根交换后child为0while (child 0){//当child小时和父亲交换 建成小堆//当child大时和父亲交换 建成大堆if (a[parent] a[child]){swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else{break;}}
} 进入向上调整函数根据我们上篇内容提供父亲和孩子之间下标的关系依次向上调整根据我们的需要和父亲孩子的大小关系用交换函数实现大/小堆。
void swap(HPDatatype* x, HPDatatype* y)
{HPDatatype tmp *x;*x *y;*y tmp;
} 为防止局部变量出交换函数作用域被销毁这里我们使用指针交换。 这种方式的缺点 1.需要动态开辟空间造成空间浪费。 2.需要完整的堆实现的代码比较麻烦不是很推荐。 我们可以使用下面的方法对上面的函数进行优化。 移动数据向上调整算法建堆
根据我们这个方法的名字就可以判断我们这个方法是不需要动态开辟额外的空间只需要使用数组下标通过向上调整算法函数来实现。
实现代码 for (int i 1; i n; i){HPadjustUp(a, i);} 这里我们将数组中的第一个数据作为一个堆通过下标的移动让后面的数字和前面的数字比较也就相相当于前面的数字作为父亲后面的数字作为孩子父亲和孩子使用向上调整函数进行调整实现堆。 像这样经过多次的移动就形成我们的堆。 无序数组从H-1层向上移动的向下调整算法建堆 上篇文章我们介绍了向下移动的调整算法但是这个算法有个前提就是除根外的左右子树都要是堆但是我们这里给定一个无序数组先让这个数组模拟成堆除根外左右子树有可能都不是堆就无法实现向下调整算法这样我们从倒数第一个非子叶结点开始向下调整也就是最后一个结点的父亲开始向下调整我们直到数组在空间中是连续的那我们从这个结点开始没向下调整依次这个结点向前移动依次这样就将一个大堆分成各个小堆完成向下调整了。
实现代码
for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);} 像这样经过多次的向下调整最终就可以实现堆。 堆排序
在实现堆排序之前我们先思考下升序和降序需要建什么堆
我们这里直接给出答案 升序建大堆 降序建小堆 问什么会是这样呢
在上篇文章中堆的删除中我们已经隐含的告诉大家了如果我们要删除堆中的数据时直接向前移动数据会造成不是原有的大堆或者小堆因此我们将根结点的数据和最后一个数据交换两个子树依然是堆然后进行向下调整size向前移动。我们不做删除这一步是不是就是排序 实现代码
int end n - 1;while (end 0){swap(a[end], a[0]);AdjustDown(a, end, 0);end--;} TOP-K问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下1. 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆 2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 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);
}// fprintf fscanfvoid 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;
}文件操作知识忘了的话自己回顾下。
今天的内容到这里就结束了感谢大家的观看可以在评论区多多交流和探讨指出我的错误
下篇文章将讲解完全二叉树的实现请大家敬请期待
