刷关键词排名seo软件软件,嘉兴seo网站建设,自适应网站举例,做网站在前面一节我们都已将堆的结构#xff08;顺序存储#xff09;已经实现#xff0c;对树的相关概念以及知识做了一定的了解。其中我们在实现删除操作和插入操作的时候#xff0c;我们还同时实现了建大堆#xff08;小堆#xff09;的向上#xff08;下#xff09;调整算法…
前面一节我们都已将堆的结构顺序存储已经实现对树的相关概念以及知识做了一定的了解。其中我们在实现删除操作和插入操作的时候我们还同时实现了建大堆小堆的向上下调整算法。
在这里我们需要补充 我们上一节实现的算法中的向上调整算法的时间复杂度为O(n*log n),而向下调整算的时间复杂度为O(n)。所以我们就可以知道在建堆的时候尽量选择时间复杂度较小的向下调整算法。
一.堆排序
小Tip排升序建大堆排升序建小堆。 1.版本一 基于已有数组进行建堆取堆顶元素完成排序。 注该版本有一个前提必须提供现有的数据结构堆。 //1.需要堆的数据结构
//2.空间复杂度 ON
void HeapSort(int* a, int n)
{HP hp; //创建一个堆for (int i 0; i n; i){HPPush(hp, a[i]); //将数组中每一个元素逐个插入堆中}//逐个取堆顶的元素int i 0;while (!HPEmpty(hp)){a[i] HPTop(hp);//取堆顶的元素HPPop(hp);//出堆}//销毁堆HPDestroy(hp);
} 基于前面我们已经实现过堆的顺序存储结构在这里我们就只实现局部代码。实现思路我在代码的旁边已经进行了标注。 2.版本二 数组进行建堆首尾交换交换之后的堆尾从堆中删除掉将堆顶数据向下调整选出次大的数据。 void HeapSort(int* a, i int n)
{//先进行向下调整算法建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, i, n);}//循环 将堆顶数据进行交换交换完将调整堆堆中的要访问的底层数组的下标减1在进行堆的调整的时候end还是 要调整的 堆中的元素个数int end end - 1;while (end){Swap(a[0], a[end]);AdustDwon(a, 0, end);end--;}
} 实现思路已经在上面的代码中已经标注了。 二 .top-k问题 如果我们要在10个数据中找前面3个最大的数据是多少咋找 如果我们要在100个数据中找前面3个最大的数据是多少咋找 如果我们要在1000个数据中找前面3个最大的数据是多少咋找 ……如果我们要在100000000000000000个数据中找前面3个最大的数据是多少咋找呢 对于数据量少的我们可以用前面所学的打擂台冒泡排序选择法排序快速排序以及上面所讲的堆排序。但是对于数据量特别大的呢我们如果还用上面所说的方法那就太慢太麻烦了。现在我们所玩的游戏有很多玩家中找积分最多的前几个玩家世界人口中找年龄最大的人……用上面的方法是不是就很繁琐了。 所以对于这种类似的问题结合堆的性质我们就Top-k来进行排序。Top-k问题即就是求数据集合中前k个最大或者最小的元素一般情况下数据量都比较大。
#include stdio.h
#include stdlib.h
void Swap(int* x, int * y)
{int temp *x;*x *y;*y temp;
}//可不用见后面
void AdjustDown(int* arr, int parent, int size)
{int child parent * 2 1;//左孩子while (child size) //注意这里的条件{//找左右孩子中值最小的 小堆用 大堆用if (child 1 size arr[child] arr[child 1]){child;}//小堆用 大堆用if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}}//top-K 问题 求最大
void topk()
{int k 0;printf(请你输入K:);scanf(%d, k);//以只读的方式打开文件const char *file data.txt;FILE* fout fopen(file, r);if (fout NULL){perror(fopen fail!);exit(1);}//用动态内存内存的知识申请k个整形单位的数组int* minHeap (int*)malloc(sizeof(int) * k);if (minHeap NULL){perror(malloc fail!);exit(2);}//从文件中读取数据for (int i 0; i k; i){fscanf(fout, %d, minHeap[i]);}//取随机生成前k个数字进行建堆 利用向下调整算法进行建堆for (int i (k-1-1)/2; i 0; i--){AdjustDown(minHeap, i, k); //建小堆}//将文件中剩余的数字和堆中的k个数据进行逐个比较大的数字王进走小的数字往出走int x 0;while (fscanf(fout, %d, x)!EOF){//如果此时读取到的数据大于堆顶数据就将if (x minHeap[0]){minHeap[0] x; //此处也可以用Swap函数进行数据的交换AdjustDown(minHeap, 0, k);}}for (int i 0; i k; i){printf(%d , minHeap[i]);}fclose(fout);
}//先生成随机数字放在文件中
void CreatData()
{int n 100000;srand((unsigned int)time(NULL));//利用时间戳进行堆随机数种子进行改变//以写的形式创建文件const char *file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fin fail!);return;}//向文件中写入用fprintf向文件中写入数字for (int i 0; i n; i){int x (rand() i) % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}
int main()
{CreatData();topk();return 0;
} 实现的思路 先实现自定义数据交换函数向下调整算法时间复杂度低所以选择它生成随机数的函数。 其次就是实现Top-K问题的核心了先定义可以自定可在所有数字要找最大的k个数字的变量k,然后再以读的形式打开所生成随机数的那个文件再就是开辟k个数据大小的数组空间。 然后先将文件中前k个数据存储在该数组中再进行将数组中的k个元素进行建堆处理此处建的是小堆。随后循环读取文件中剩余的数据直到遇到文件结束的标志每一次将从文件中读取中的数据和小堆的堆顶进行比较大小如果比堆顶数据大就将该值堆顶位置或者交换。于此同时之后每次还得数据调整一直保持小堆。读取完比较调整完之后将最终数组中的数据打印在终端上。最终需要关闭文件哦 注 对于Top-k 问题如果求前K个最大的数据就建小堆反之就建小堆。 》》 》》》》》》》》》 今天分享的内容就结束了下篇见》》》》》》》》》》》》》》》
关注博主优质内容不断更新
如有错误还望指出
