个人微网站怎么做,汕头外发加工网,百度开户公司,北京海淀互联网公司1.堆排序
想法⼀#xff1a;
基于已有数组建堆、取堆顶元素完成排序。也就是利用写好的堆数据结构#xff08;之前的文章有讲解#xff09;#xff0c;去实现排序。
void HeapSort(int* a, int n){HP hp;for(int i 0; i n; i){HPPush(hp,a[i]);}int i 0;whi…1.堆排序
想法⼀
基于已有数组建堆、取堆顶元素完成排序。也就是利用写好的堆数据结构之前的文章有讲解去实现排序。
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);
先依次入堆然后再将堆顶数据依次取出为大堆即是降序小堆为升序。实际上这种方法使用起来是很不方便的必须要有堆的数据结构而且时间复杂度为On。
想法⼆
数组建堆⾸尾交换交换后的堆尾数据从堆中删掉将堆顶数据向下调整选出次⼤的数据。
void HeapSort(int* arr, int n)
{//根据给定的arr来进行建堆//child:n-1 parent:(n-1-1)/2向下调整算法建堆//for (int i (n - 1 - 1) / 2; i 0; i--)//O(n)//{// AdjustDown(arr, i, n);//O(logn)//}//向上调整建堆for (int i 0; i n; i){AdjustUp(arr, i);}//堆排序//排升序---建大堆//排降序---建小堆int end n - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, 0, end);end--;}}
这里利用的是堆的思想而不是直接用堆来排序首先要建堆将传进来的数组入堆这里以建小堆为例利用向下调整的方法将一个个依次调整直到直到根节点 这里完成了建堆那后面接下来排序怎么办其实利用思想将堆顶元素与最后一个元素交换再将元素个数减一将剩余的堆进行调整依次交换直到到堆顶。最后发现建的小堆其实是降序排列反之降序是建小堆。
这样就排序完成。
注意这里考虑一个问题向上调整可以建堆向下调整也可以建堆那个时间复杂度更低。
1.2向上调整算法和向下调整算法比较
向上调整算法 往下结点个数逐渐增多向下调整次数增多 可以推出向上调整建堆时间的复杂度O(n*logn)
向下调整算法 可以推出向下调整建堆时间的复杂度On
比较发现向下调整算法更优。
2.TOP-K问题
TOP-K问题即求数据结合中前K个最⼤的元素或者最⼩的元素⼀般情况下数据量都⽐较⼤。 ⽐如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的⽅式就是排序但是如果数据量⾮常⼤排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决基本思路如下
第一步⽤数据集合中前K个元素来建堆
这和前面堆排序有一些相似
前k个最⼤的元素则建⼩堆
前k个最小的元素则建⼤堆
第二步⽤剩余的N-K个元素依次与堆顶元素来⽐较不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后堆中剩余的K个元素就是所求的前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 error);exit(1);}//找最大的前K个数建小堆int* minHeap (int*)malloc(sizeof(int) * k);if (minHeap NULL){perror(malloc fail!);exit(2);}//读取文件中前K个数据建堆for (int i 0; i k; i){fscanf(fout, %d, minHeap[i]);}//建堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(minHeap, i, k);}//遍历剩下的n-k个数据跟堆顶比较谁大谁入堆//调整堆int x 0;while (fscanf(fout, %d, x) ! EOF){if (x minHeap[0]){minHeap[0] x;AdjustDown(minHeap, 0, k);}}for (int i 0; i k; i){printf(%d , minHeap[i]);}fclose(fout);
}
这里一些文件操作函数可以看看小编前面的文章有讲解。
