给出N个数据，要求找到并输出这N个数里面最大的K个数
思路：利用堆，先建一个开辟一个大小为K的数组，从N个数据里拿出K个数据放到堆里面，然后再通过向
下调整法把堆调整为最小堆，此时数组的第一个元素就是堆里面最小的元素，然后在剩下的N-K个
数据中依次和堆里面最小的数据进行比较，若比第一个元素大，则交换两个的值，每交换一次就向下调
整一次，保证在最上面的是最小元素，这样一直到所有数据比较完毕，此时堆里面存储的k个数据就是最
大的k个数据。
下面是实现代码
计算
安全
数据库
网络和加速
企业服务
#include<iostream>#include<algorithm>using namespace std;//1.在N个数据当中找出最大的K个数const int N = 10000;const int K = 100;void AdjustDown1(int a[], int size, int parent) //建一个小堆{ int child = parent * 2 + 1; while (child < K) { if ((child + 1 < K) && (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 GetTopK(int a[],int TopK[]){ assert(K < N); int i = 0; int j = 0; int m = 0; int n = 0; for (i = 0; i < K; i++) { TopK[i] = a[i]; //取出a中的前k个数字放到topk[]里面 } //建堆 for (j = (K - 2) / 2; j >0; --j) { AdjustDown1(TopK,K,j); } for (int m = 0; m < N; ++m) { if (a[m]>TopK[0]) { TopK[0] = a[m]; AdjustDown1(TopK, K, 0); } } for (int n = 0; n < K; ++n) //一次输出K个最大数 { cout << TopK[n] << " "; } cout << endl;}测试代码
#include"BIgData.h"void TestTopK(){ int a[N]; int TopK[K]; for (int i = 0; i < N; ++i) { a[i] = i; } GetTopK(a, TopK);}int main(){ TestTopK(); system("pause"); return 0;}测试结果
为了便于调试，我用的测试栗子比较简单，大家可以尝试一下更一般的栗子哦~
二.堆排序
思路：利用堆，建一个最大堆，每次选出最大的数据与数组末尾的数据进行交换，然后再进行一次向下
调整变成最大堆，始终保持最上面的为当前最大的数据，假设数组由n个数据，则下次就让第一个数据与
数组的第n-1个数据作比较，因为第n个数据已经是最大的了，每交换一次要调整一次，这样当比较到第
一个数据时这个堆就是一个有序的了。
实现代码如下：
//2.堆排序：建大堆，每次找到最大的数据交换到数组末尾，将剩下的数据AdjustDown，再进行交换void AdjustDown2(int a[],int size,size_t parent){ int child = parent * 2 + 1; while (child<size) { if ((child + 1 < size)&&a[child] < a[child + 1]) { ++child; } if (a[child] > a[parent]) { swap(a[child], a[parent]); parent = child; child = parent * 2 + 1; } else { break; } }}void Heap_Sort(int a[], size_t n){ for (int i = (n - 2) / 2; i >= 0; i--) //注意边界条件 { AdjustDown2(a, n, i); } for (int i = 0; i < n; ++i) { swap(a[0], a[n - 1-i]); AdjustDown2(a, n - 1 - i, 0); } for (int i = 0; i < n; ++i) { cout << a[i] << " "; } cout << endl;}测试代码：
void TestHeap_Sort(){ int a[] = { 10, 12, 9, 15, 13, 17, 16, 18, 20,14 }; Heap_Sort(a, 10);}int main(){ TestHeap_Sort(); system("pause"); return 0;}测试结果：
以上便是堆的两种简单应用啦，不足之处还请大家指出哦~
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
