应用背景
生活中我们每每都会遇到Top-K问题，例如搜索附近前几的的动漫，频率前几的搜索词条等等
- 示例：
如果只是数据比较少的，我们可以排序找到前几的数据，但是实际应用中我们时常都会面对海量的数据，大到内存无法全部加载，这就需要我们用数据结构中的堆来解决
处理策略
- 首先我们知道：
对于大堆，堆顶的数据一定是堆里面数据中最大的；对于小堆，堆顶的数据一定是堆里面数据中最小的
对于找最大前k：
利用小根堆维护一个大小为K的数组，目前该小根堆中的元素是排名前K的数，其中根是最小的数
此后，每次从数据中取一个元素与根进行比较，如大于根的元素，则将根元素替换并进行向下调整（下沉）
即保证小根堆中的元素仍然是排名前K的数，且根元素仍然最小（否则不予处理）
时间复杂度
总结：该算法的时间复杂度是(nlogk)
首先需要对K个元素进行建堆，时间复杂度为O(k)
建堆复杂度证明：
然后要遍历数据,最坏的情况是每个元素都与堆顶比较并排序，需要堆化n次
每次最差都下调高度次，而高度为log（k），所以是O(nlog(k))
因此总复杂度是O(k+nlog(k))，也就是O(nlogk)
过程及实现代码
- 图示过程：
参考代码：
// TopK问题：找出N个数里面最大/最小的前K个问题 // 找最大的前K个，建立K个数的小堆 // 找最小的前K个，建立K个数的大堆 void PrintTopK(int* a, int n, int k)//对大的前K { HP hp; HeapInit(&hp); for (int i = 0; i < k; i++)//建立一个小堆 { HeapPush(&hp, a[i]); } for (int i = k; i < n ; i++) { if (HeapTop(&hp) < a[i])//比较和调整（维护堆，保证始终是最大的前K） { hp.a[0] = a[i]; AdjustDown(hp.a, k, 0); } } HeapPrint(&hp); }
测试
- 测试代码：
void TestTopk() { int n = 1000000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); for (size_t i = 0; i < n; ++i)//产生一万个数据 { a[i] = rand() % 1000000;//都比100w小的数 } // 再去设置10个比100w大的数（随机设置） a[5] = 1000000 + 1; a[1231] = 1000000 + 2; a[5355] = 1000000 + 3; a[51] = 1000000 + 4; a[15] = 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);//打印 }
结果示图：
堆源码
注：C语言堆的实现
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //默认堆中的数据类型 typedef int HPDataType; //堆结构体类型 typedef struct Heap { HPDataType* a;//数组指针（指向动态开辟的空间） int size;//堆中存放的数据个数 int capacity;//堆的容量（数组长度） }HP; //堆初始化 void HeapInit(HP* hp); //堆销毁 void HeapDestroy(HP* hp); //入堆 void HeapPush(HP* hp, HPDataType x); //出堆 void HeapPop(HP* hp); //堆数据打印 void HeapPrint(HP* hp); //堆顶数据 HPDataType HeapTop(HP* hp); //堆存入数据个数 int HeapSize(HP* hp); // 堆的判空 bool HeapEmpty(HP* hp); //交换函数 void Swap(HPDataType* a, HPDataType* b); //数据调整(实现大堆) void AdjustUp(HPDataType* a, int child); //数据调整 void AdjustDown(HPDataType* a, int size, int parent); //堆初始化 void HeapInit(HP* hp) { assert(hp);//避免传入参数错误 //初始化 hp->a = NULL; hp->size = hp->capacity = 0; } //堆销毁 void HeapDestroy(HP* hp) { assert(hp);//避免传入参数错误 //释放 free(hp->a); hp->capacity=hp->size=0; } //数据调整 void AdjustUp(HPDataType* a, int child)// { int parent = (child - 1) / 2; while (child) { if (a[parent] > a[child])//不符合情况交换 Swap(&a[parent], &a[child]); else break; //调整下标 child = parent; parent = (child - 1) / 2; } } //数据调整 void AdjustDown(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child<size) { //找到数据小的儿子 if (child + 1 < size && 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 HeapPush(HP* hp, HPDataType x) { assert(hp);//避免传入参数错误 //满堆的情况 if (hp->size == hp->capacity) { //如果容量为0则开辟4个空间，否则扩展成原来的两倍 int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HP* tmp = (HP*)realloc(hp->a, sizeof(HP) * newcapacity); if (tmp == NULL)//开辟失败则打印错误并结束进程 { perror("realloc fail:"); exit(-1); } hp->capacity = newcapacity; hp->a = tmp; } //入堆操作 hp->a[hp->size] = x;//入尾端，再调整 hp->size++; //数据调整 AdjustUp(hp->a, hp->size - 1);//传入数组地址和下标 } //出堆（删除堆顶的数据） void HeapPop(HP* hp) { assert(hp);//避免传入参数错误 assert(hp->size);//空堆的情况 Swap(&hp->a[0], &hp->a[hp->size - 1]);//先将堆顶数据与堆尾交换 hp->size--;//再将记录数据个数变量减减实现删除的效果 //对现在堆顶的数据进行下调 AdjustDown(hp->a, hp->size, 0); } //堆数据打印 void HeapPrint(HP* hp) { assert(hp);//避免传入参数错误 for (int i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); }printf("\n"); } //堆存入数据个数 int HeapSize(HP* hp) { assert(hp);//避免传入参数错误 return hp->size; } // 堆的判空 bool HeapEmpty(HP* hp) { assert(hp);//避免传入参数错误 return hp->size==0; } //交换函数 void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; }
有问题欢迎留言，可以的话留下你的三连哦！
