TopK Question

✅作者简介：大家好我是zoroxs
📃个人主页：c/c++学习之路
🔥💖如果觉得博主的文章还不错的话，请👍三连支持一下博主哦

TopK Question

💛什么是TopK问题

topK问题是一个非常经典的问题,
顾名思义,就是在前N个数中找最大的(最小的)前k个元素 —>我们这里找最大的
这个问题现实中是经常会碰到的,比如在京东中购物,电脑top10就是前10热卖…

🧡方式一

这都不用说, 第一个思路大多数人一定会想到排序, 降序排序之后就很好地取k个就可以了

我们使用快速排序的时间复杂度最低,O(N* logN)
这种方法复杂度过于高,如果数据量大太耗费资源,所以不予采用

大家自己实现

💚方式二 大堆

我们在数据结构中学习过堆,堆在逻辑结构上是完全二叉树
堆有两个性质

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

这就是堆的两种可能,相信大家就已经想到了思路

创建一个大堆,将N个数全部入堆,依次取堆顶的数据,删除堆顶的数据,取到的就是前k个最大的

这个算法的时间复杂度是 O(N + K*log N )
代码看一下

/*
    将每一个数都插入大堆中,取k次堆顶的数据 o(n + k*logn)
*/voidheaptopk1(int*a,int n,int k){assert(a);

    Heap hp;HeapInit(&hp);//把所有数据插入堆中for(int i =0; i < n; i++){HeapPush(&hp, a[i]);}while(k--){printf("%d ",HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);}

此时抛出一个问题?

如果需要在14亿个数中找前100个, 那该怎么处理呢?
开辟14亿大小的堆?? 排序?? 这些都不适用

所以有大神提出了方式三

❤️方式三 妙手

思路是这样的

我们要找N个数中的最大的前k个数,
创建一个小根堆,先让前k个元素入堆,剩余元素挨个和堆顶的数据比较,如果大于堆顶的数据,就删除堆顶的数据,入堆

我们来分析一下

空间复杂度虽然说是O(K) ,但是一般这种问题,K << N , 所以与方式二的差距很大,而且这里并不需要全把数据存下来.
看一下代码实现

voidHeapTopK2(int* a,int n,int k){assert(a);
    Heap hp;HeapInit(&hp);//将k个数据插入堆中for(int i =0; i < k; i++){HeapPush(&hp, a[i]);}//拿之后的数据依次和堆顶比较for(int i = k; i < n; i++){//如果大于堆顶元素,删除堆顶元素,入堆if(a[i]>HeapTop(&hp)){HeapPop(&hp);HeapPush(&hp, a[i]);}}HeapPrint(&hp);HeapDestroy(&hp);}

💕总结

大家可以画图自己分析分析,多思考,有问题请与我交流

🔥💖如果觉得博主的文章还不错的话，请👍三连支持一下博主哦