TOP-K问题：即求数据结合中前K个最大数或者最小数，一般情况下数据量比较大。常用的方法是建堆处理
①.生活案例
在生活中有很多涉及top-k问题，比如世界五百强，学校专业前几名，富豪榜等等。
对于TOP-K问题，可能第一反应是用排序，将前几名排序出来，但当数据量很大很大时，排序就不好处理了。可能数据一下不能完全加载到内存中去。
而解决这样的问题，最好的方式是用堆来处理。
②.解决思路:
1.取数据集合中前K个元素建堆
◽ 获取前K个最大数 ，则建小堆。
◽ 获取前K个最小数， 则建大堆
void AdjustDown(int* a, int n, int parent)//实现的前提是左右子树都是堆 { int child = parent * 2 + 1; while (child < n) { //选出左右孩子中比较大的孩子，假设child为左边，假设左边孩子比较xiao if (child + 1 < n && a[child] > a[child + 1])//不过这里存在越界的风险，不能保证右边的孩子一定存在 {//右边的孩子要存在的话也需要小于n才可以所以我们再加上去 ++child;//让右边的孩子成为比较大的child } //然后让根（父亲）与较大儿子比较，这里是大堆，父亲要大于儿子的 if (a[parent] >a[child]) { Swap(&a[parent], &a[child]); //交互完后，让parent跳到儿子位置上去，儿子继续往下找 parent = child; child = parent * 2 + 1; } else { break; } } }
// 1. 建堆--用a中前k个元素建堆 for (int i = (k - 2) / 2; i >= 0; i--) { AdjustDown(a, k, i); }
2.用剩余的n-k个数据与堆顶元素比较，不满足则替代入堆
将剩下的n-k数据依次比较完后，堆里的数据就是所求的前K个最大或最小的元素。
如果我们需要前K个最大数，那要求建小堆，为什么呢？
小堆堆顶数据应该是比较小的数据，而当剩下的n-k个数据与堆顶数据比较时，当数据大于堆顶数据时，就代替它入堆，入堆后，根据堆的性质，这个数就会往堆的下面走，而堆顶数据则是更新为比这个数据较小的值。
接着进行比较，当数据都比较完时，堆里的数据就是我们想要的前K个最大数。
因为当有一个较大数过来与堆顶比较时，它肯定会替代堆顶元素然后入堆，入完堆后，就会在堆里向下调整，因为这是个小堆，要求父节点值小于子结点，所以它肯定会在下面。并且如果这个值是最大值，它就会跑到堆的最后面去。次大的数就会跑到堆的尾部位置，在最大的前面。
就是根据这个原理，我们可以选出前K个最大数。
选出前K个最小数，原理也相似，建个大堆即可。
首先将大堆的图形想象出来，大堆上面较大，下面较小。
当一开始从数据集合中选出K个建堆后，剩下的n-k开始与堆顶元素比较
当剩下的数据比堆顶元素小时，就代替堆顶数据入堆，入堆的这个数据就会往下走，某个比它大的值就变成堆顶元素，接着比较，如果来了一个最小值，则它必然会替代堆顶元素入队，并且入堆后，就会向下调整到堆的最后面前。
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 for (int i = k; i < n; i++) { if (a[i] > a[0]) { a[0] = a[i]; AdjustDown(a, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", a[i]); }
③.快速测试代码
我们可以生成一个数组，这个数组拥有10000个数字，每个数字都不超过1000000，然后我们想要获取前10最大的数，拿这个例子来测试代码，只要我们随便改变数组中10个值，让它大于1000000，那得到的结果肯定就是这些值了，这样可以做到快速测试代码。
#include <time.h> void PrintTopK(int* a, int n, int k) { // 1. 建堆--用a中前k个元素建堆 for (int i = (k - 2) / 2; i >= 0; i--) { AdjustDown(a, k, i); } // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 for (int i = k; i < n; i++) { if (a[i] > a[0]) { a[0] = a[i]; AdjustDown(a, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", a[i]); } } void TestTopk() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); for (size_t i = 0; i < n; ++i) { a[i] = rand() % 1000000;//生成1000000以内的随机数 } a[5] = 1000000 + 1;//随机改动10个值，让这几个值都大于1000000 a[1231] = 1000000 + 2; a[531] = 1000000 + 3; a[5121] = 1000000 + 4; a[115] = 1000000 + 5; a[2335] = 1000000 + 6; a[9999] = 1000000 + 7; a[76] = 1000000 + 8; a[423] = 1000000 + 9; a[3144] = 1000000 + 10; PrintTopK(a, n, 10);//最后获得前K个最大的数字就是我们改动的数字 } int main() { TestTopk(); return 0; }
