Topk
在n个数中找出最大的前K个 or 在n个数中找出最小的前K个
（n>K）
1000个数中找到最大的前十个
方式1：
先排降序，前十个就是最大的。时间复杂度O(N*log2N)
方式2：
N个数依次插入大堆，PopK次，每次取堆顶的数据就是最大的前K个。时间复杂度O(N+log2N)（下篇证明）
方式3：
假设N非常大，N是10亿，内存中存不下这些数，他们存在文件中，k是100。那么方式1与方式2就都不可以用了。时间复杂度 O(K+(N-K)log2K)
10亿整数我们看看大概消耗多少空间
1.用前K个数建立一个K个数的小堆
2.用剩下的N-K个数，依次跟堆顶的数据进行比较，如果比堆顶的数据大，就去替换堆顶的数据，在向下调整
3.最后堆里面K个数就是最大的K个数
Topk打印函数TopkPrint
void TopkPrint(int* a, int n, int k) { //创建一个堆 HP hp; //堆初始化 HeapInit(&hp); //用前K个数建立一个K个数的小堆 int i = 0; for (i = 0; i < k; i++) { HeapPush(&hp,a[i]); } //用剩下的N-K个数，依次跟堆顶的数据进行比较，如果比堆顶的数据大，就去替换堆顶的数据，在向下调整 //替换就破坏结构了，我们用接口来实现，找到就先pop，然后push大的数就行 for (i = k; i < n ; i++) { //堆顶元素小于数组中的数 if (HeapTop(&hp) < a[i]) { //先把堆顶的数给出掉 HeapPop(&hp); //再插入这个数组中的数进堆 HeapPush(&hp, a[i]); } } //然后打印堆即可 HeapPrint(&hp); HeapDestroy(&hp); }
没有修改的接口见 算法给小码农堆魂器–铁血柔情
改掉的接口
向上调整函数
//向上调整函数 void AdjustUp(HPDataType* a, int size, int child) { assert(a); int parent = (child - 1) / 2; #if HEAP while (child > 0) { if (a[parent] < a[child])//父亲小于孩子就交换（大堆） { Swap(&a[parent], &a[child]); //交换好后重新称呼一下孩子与父亲 child = parent; parent = (child - 1) / 2; } else { break; } } #elif !HEAP while (child > 0) { if (a[parent] > a[child])//父亲大于孩子就交换（小堆） { Swap(&a[parent], &a[child]); //交换好后重新称呼一下孩子与父亲 child = parent; parent = (child - 1) / 2; } else { break; } } #endif // HEAP }
向下调整函数
//向下调整函数 void AdjustDown(HPDataType* a, int size, int parent) { assert(a); //创建一个孩子变量，有两个孩子就在这个上加1就行 int child = parent * 2 + 1; #if HEAP 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; } } #elif !HEAP 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; } } #endif // HEAP }
然后在Heap.h文件中加入
//0 大堆模式 1小堆模式 #define HEAP 0
