- 建堆的两种方法
- 这里会用到前面的向上/向下调整/交换函数。
堆排序
整体思路
- 建堆（直接把数组搞成堆）升序：建大堆 降序：建小堆
- 利用堆删除的思想来进行堆排序 （就是模拟堆删除的过程，但是实际并不删除堆）
- 1：交换头尾
- 2：向下调整（除去最后一个元素&&最后一个元素已经排好序了）
- 3：循环重复上述过程
- 建队有两种方法：插入（向上调整建堆）/向下调整建堆（下篇细讲）
- 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
代码实现
//堆排序:本质直接在数组里面排序 void test1(int* a, int size) { //方法1的时间/空间复杂度都很低 //方法2 //1.向上调整建堆 建堆--建的小堆--降序 建大堆--升序 for (int i = 0; i < size; i++) { AdjustUp(a, i); } //1.向下调整建堆 for (int i = (size - 1 - 1) / 2; i >= 0; i--)//i=0的时候到达根节点此时就是全部向下调整 { Adjustdown(a, size, i);//这里的size不确定，但是肯定比size小所以取最大就size } //2. while (size) { //交换 Swap(&a[0], &a[size - 1]); //向下调整(除去已经排序好的元素） Adjustdown(a, size-1, 0); //到达下一个交换的位置 size--; } } int main() { int a[10] = { 2,3,7,5,4,3,9,7,6,10 }; int size = sizeof(a) / sizeof(a[0]);//10个数==最后一个数的下一个数的下标 test1(a, size); //3.打印 for (int i = 0; i < size; i++) { printf("%d ", a[i]); } return 0; }
Q1建大堆/小堆
升序：建大堆
降序：建小堆
Q2数据个数和下标
size：指向最后一个元素的下一个位置
交换首位元素：最后一个元素的下标size-1
出去排好的元素向下调整个数：为size-1（-1除去排好的元素）
TopK问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
整体思路
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆；前k个最小的元素，则建大堆
- 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
- 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
代码实现
void CreateDate()//创造数据 { int n = 1000000; srand((unsigned int)time(NULL));//随机数的种子 //打开文件 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 r = (rand() + i) % 1000000; fprintf(fin, "%d\n", r); } //关闭文件 fclose(fin); } void test2(int K) { //打开文件 const char* file = "data.txt";//文件指针 FILE* fout = fopen(file, "r");//以写的形式打开文件状态指针 if (fout == NULL)//打开失败 { perror("fopen error"); return; } //读取文件 //开辟数组空间存放小堆 int* a = (int*)malloc(sizeof(int) * K); if (a == NULL) { perror("malloc error"); return; } for (int i = 0; i < K; i++) { fscanf(fout, "%d", &a[i]);//读取放入数组 AdjustUp(a, i);//建小堆 } //一直读取并且比较 int n = 0; while (fscanf(fout,"%d", &n) != EOF) { if (a[0] < n) { a[0] = n; Adjustdown(a, K, 0); } } //打印 int i = 0; for (i = 0; i < K; i++) { printf("%d ", a[i]); } //释放空间/关闭文件 free(a); fclose(fout); } int main() { //CreateDate();//创造数据 int K = 8; test2(K);//TopK问题--小堆--取前K个最大的数 return 0; }
Q1造数据CreateData
- 打开文件
- 写文件
- 关闭文件
- 随机数&随机数的种子&产生随机数
- 随机数最多3万个
- 文件指针&文件状态指针
- 想要产生的随机数在100万以内：%100万
- 测试：去文件里面修改值大于>100万的数，查看是否打印出来的是修改后的数据。
void CreateDate()//创造数据 { int n = 1000000; srand((unsigned int)time(NULL));//随机数的种子 //打开文件 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 r = (rand() + i) % 1000000; fprintf(fin, "%d\n", r); } //关闭文件 fclose(fin); }
Q2建大堆/小堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
🙂感谢大家的阅读，若有错误和不足，欢迎指正
