专业俄语网站设计,python的基本语法,安卓android软件,2017做哪些网站致富目录
前言
top K问题
模拟数据
建堆
验证#xff08;简单了解即可#xff09;
最终代码
调试部分 前言
在大小堆的实现#xff08;C语言#xff09;中我们讨论了堆的实际意义#xff0c;在看了就会的堆排序#xff08;C语言#xff09;中我们完成了堆排序#…目录
前言
top K问题
模拟数据
建堆
验证简单了解即可
最终代码
调试部分 前言
在大小堆的实现C语言中我们讨论了堆的实际意义在看了就会的堆排序C语言中我们完成了堆排序在这一篇中我们会接着完成堆的第二个实际意义top K问题本篇中涉及的关于文件操作函数fprintf、fclose请查看文件操作函数---C语言版本本篇中涉及的关于随机数函数time、rand、srand的使用请查看time、rand和srand函数及应用C语言
top K问题
问题描述获取N个数里找最大的前K个数N远大于K 解决思路一 N个数插入进大堆中Pop K次 时间复杂度N*logN K*logN O(N*logN) 但如果N为100亿100亿个整数需要40GB左右的内存空间而只要查找前10个数K为10 解决思路二 1、取前K个值建立K个数的小堆 2、再读取后面的值跟堆顶元素比较若大于堆顶元素交换二者位置然后重新堆化成小堆若不大于堆顶元素则不进堆进行下一次的比较重要 时间复杂度O(N*logK) 注意事项必须要建立小堆不能建立大堆如果建立大堆一旦第一大的数字在建堆时位于堆顶后续第n大的数字就无法进堆同时第二大的数字可能还会被挤出去如果不信可以用[4,6,1,2,8,9,5,3]这个我随机想出来数组用以上方法取前三个最大的数字试一试 有时候你可能会很想刨根问底的知道这些办法都是怎么想出来的其实我也不知道这就跟你骑自行车的时候去思考这些链子为什么要这样组合在一起为什么组合在一起就可以产生这样的效果其实我们根本不需要思考那么多我们只需要骑上自行车去干我们要干的事情即可它只是一个用于解决我们问题的工具我们说的解题思路也是一样的这些东西都是哪些很nb的人发明出来的如果你是一个很nb的人你也不会看到这里不是前人栽树后人乘凉作为一个还没有完全深入学习数据结构的菜鸟既然已经知道了有这种解决办法那么你就直接用等你什么时候感觉自己已经很nb了再来思考为什么吧......当然也不是说都不要思考一些必要的思考还是需要的别钻牛角尖了 模拟实现 使用数组[7, 8, 15, 4, 20, 23, 2, 50]演示如何使用最小堆找出前3个最大的元素。 首先我们创建一个小堆并将数组的前3个元素[7, 8, 15]插入堆中初始堆的表示如下 7/ \8 15 接下来遍历数组发现 4 7因此我们不做任何操作 继续遍历数组发现 20 7因此将 7 替换为 20 并重新堆化成小堆 8/ \20 15 继续遍历数组发现 23 大于 8因此我们将 8 替换为 23 并重新堆化成小堆 15/ \20 23 继续遍历数组发现 2 15因此我们不做任何操作 继续遍历数组发现 50 15因此我们将 15 替换为 50 并重新堆化成小堆 20/ \50 23 最后数组遍历完成得到了最终的小堆 20/ \50 23 此时堆中的前3个最大元素为 [20, 50, 23]它们就是原数组中的前3个最大元素 模拟数据
1、利用srand、time、rand函数生成10000000个随机数据并写入data.txt文件中
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include time.h
#include windows.h
#include stdlib.h//造数据
void CreatNData()
{int n 10000000;srand(time(0));//造数据FILE* pf fopen(data.txt, w);if (pf NULL){perror(fopen error);return;}for (int i 0; i n; i){int x (rand() i) % 10000000;fprintf(pf, %d\n, x);}fclose(pf);
}int main()
{CreatNData();return 0;
} 关于“i”的解释使用变量 i 可以在每次生成随机数时引入一个不同的偏移量从而避免产生重复的随机数序列。如果没有这个偏移量相同的 rand() 调用将始终得到相同的结果。通过引入一个变化因子如 i来修改随机数生成过程可以增加随机性并且在循环或多次调用中产生不同的结果。这对于某些应用场景例如密码学、模拟和游戏等可能非常重要因为它们需要高度不确定性和独立性简单来讲就是防止生成的随机数重复。 建堆
1、获取指向存放了一千万个随机整数的文件地址
2、由于vs2022不支持C99的变长数组所以需要手动申请k个空间用于建堆
3、读取文件中的前k个数据利用向上调整函数模拟堆插入的过程建堆
4、利用while循环从第k1个数开始因为前面已经用fscanf函数读取了前k个数逐个读取文件中的数字直到读取到文件末尾读取成功的值会被赋值给指定的变量x然后将x与此时堆顶元素也就是数组的首元素比较如果该元素大于堆顶元素就让该元素进堆并进行向下调整确保小堆的性质不会改变
5、读取完毕后打印数组前k个元素即打印堆的前k个结点
//打印前k个数
void PrintTopK(const char* file, int k)
{FILE* fout fopen(file, r);if (fout NULL){perror(fopen error);return;}//建有k个数的小堆int* a (int*)malloc(sizeof(int) * k);if (a NULL){perror(melloc error);return;}//读取前k个数建堆for (int i 0; i k; i){fscanf(fout, %d, a[i]);AdjustUP(a, i);}//调堆int x 0;while (fscanf(fout, %d, x) ! EOF){if (x a[0]){a[0] x;AdjustDown(a, k, 0);}}//打印堆for (int i 0; i k; i){printf(%d , a[i]);}printf(\n);fclose(fout);
}关于”fscanf(fout, %d, x)“的解释fscanf函数允许从指定文件流中按照指定格式读取数据并将其赋值给相应变量通俗来讲就是每次调用 fscanf 函数都会尝试从文件中读取一个数据项并根据提供的格式进行解析和赋值如果希望实现循环逐个读取文件中的多个数据项需要结合循环语句来重复调用 fscanf 函数。 验证简单了解即可 为了检验我们选出是否真的是1~10000000的随机整数我们可以通过将文件中随意的五个数改为五个间谍数10000001、10000002、10000003、10000004、10000005然后再次程序 只列举出来一个10000004其余的都有 可以看到五个大于10000000的间谍数成功的被选出来了
解释因为我们之前选的数都是1~10000000之间的随机整数我们不确定选的数到底有没有超出这个范围所以可以找几个刚好紧挨10000000的间谍数如果超过了
最终代码
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include time.h
#include windows.h
#include stdlib.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a; //指向存储元素的指针int capacity; //当前顺序表容量int size; //当前顺序表的长度
}HP;//交换父子位置
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType* tmp *p1;*p1 *p2;*p2 tmp;
}//向上调整此时传递过来的是最后一个孩子的元素下标我们用child表示
void AdjustUP(HPDataType* a, int child)
{//由于我们要调整父亲与孩子的位置所以此时也需要父亲元素的下标而0父亲元素的下标值 任意一个孩子的下标值-1/ 2 int parent (child - 1) / 2;//当孩子等于0的时位于树顶数组首元素的位置树顶元素没有父亲循环结束while (child 0){//如果孩子还未到顶且它的下标对应的元素值小于它的父亲的下标对应的元素值就将父子位置交换交换玩后还要将下标对应的值“向上移动”if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}//由于这是一个小堆所以当孩子大于等于父亲时不需要交换直接退出循环即可else{break;}}
}//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{//根据之前的推论左孩子的下标值为父亲下标值的两倍1左孩子的下标值为父亲下标值的两倍2int child parent * 2 1;//循环结束的条件是走到叶子结点while (child size){//假设左孩子小若假设失败则更新child转换为右孩子小同时保证child的下标不会越界//if (child 1 size a[child 1] a[child])它也是if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){//如果此时满足孩子小于父亲则交换父子位置同时令父亲的下标变为此时的儿子所在下标儿子所在下标变为自己的儿子所在的下标向下递归Swap(a[child], a[parent]);parent child;child parent * 2 1;}//如果父亲小于等于左孩子就证明删除后形成的新堆是一个小堆不再需要向下调整算法循环结束else{break;}}
}//造数据
void CreatNData()
{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);
}//打印前k个数
void PrintTopK(const char* file, int k)
{FILE* fout fopen(file, r);if (fout NULL){perror(fopen error);return;}//建有k个数的小堆由于vs2022不支持C99的变长数组所以这里需要手动malloc建堆int* a (int*)malloc(sizeof(int) * k);if (a NULL){perror(melloc error);return;}//读取前k个数建堆for (int i 0; i k; i){fscanf(fout, %d, a[i]);AdjustUP(a, i);}//调堆int x 0;while (fscanf(fout, %d, x) ! EOF){if (x a[0]){a[0] x;AdjustDown(a, k, 0);}}//打印堆for (int i 0; i k; i){printf(%d , a[i]);}printf(\n);fclose(fout);
}int main()
{//CreatNData();PrintTopK(data.txt,5);return 0;
}调试部分
1、选出前五个数并建堆 2、从第k1个数开始读取然后与堆顶元素进行比较大于堆顶元素就与堆顶元素交换小于堆顶元素则不交换并读取下一个数与堆顶元素比较
3、28230大于253交换进堆 4、 28230进堆并利用向下调整算法调整堆性质为小堆后继续读取下一个数这里是791 关于时间复杂度的计算我们放在了堆的相关时间复杂度的计算C语言中里面还有向上调整算法与向下调整算法实现堆排序的时间复杂度计算过程
~over~
