济宁网站建设平台,做论坛推广的网站,wordpress后台 502,WordPress文章内容彩色目录
一、前言
二、Top-k问题 #x1f4a6;解法一#xff1a;暴力排序
#x1f4a6;解法二#xff1a;建立N个数的堆
#x1f4a6;解法三#xff1a;建立K个数的堆#xff08;最优解#xff09;
三、完整代码和视图
四、共勉 一、前言 在之前的文章中#xff…目录
一、前言
二、Top-k问题 解法一暴力排序
解法二建立N个数的堆
解法三建立K个数的堆最优解
三、完整代码和视图
四、共勉 一、前言 在之前的文章中已经详细的讲解了二叉树、堆、堆排序。那么关于堆还有一个比较有意思的题就是TopK问题。 如果对堆和二叉树还不够了解的可以看看我之前的文章哦 详解二叉树和堆 二、Top-k问题 Top-k问题在 N 个数中找出前 K 个最大/最小的元素一般情况下数据量 N 都远大于 k。 Top-k问题在生活中是非常的常见比如游戏中某个大区某个英雄熟练度最高的前10个玩家的排名我们就要根据每个玩家对该英雄的熟练度进行排序可能有200万个玩家但我只想选出前10个要对所有人去排个序吗显然没这个必要。 再比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 解法一暴力排序
对于Top-K问题首先想到的最简单直接的方式就是排序。
我们用堆排序其时间复杂度为O(N*log2N)。
但是如果数据量非常大排序就不太可取了可能数据都不能一下子全部加载到内存中。 解法二建立N个数的堆
建一个 N 个数的堆C中可用优先级队列priority_queue不断的选数选出前 k 个。
时间复杂度建N个数的堆为O(N)获取堆顶元素 (也即是最值) 并删除掉堆顶元素为O(log2N)上述操作重复 k 次所以时间复杂度为O(Nk*log2N)。
【思考】
能否再优化一下呢假设 N 是 10 亿数内存中放不下是放在文件中的。前面两个方法都不能用了。 解法三建立K个数的堆最优解 ✨基本思想 用数据集合中前K个元素来建堆。 找前 k 个最大的元素则建小堆 找前 k 个最小的元素则建大堆 用剩余的 N-K 个元素依次与堆顶元素来比较不满足则删除堆顶元素再插入。 找前 k 个最大的元素大于堆顶元素则删除堆顶元素再插入 找前 k 个最小的元素小于堆顶元素则删除堆顶元素再插入 将剩余的 N-K 个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 ✨时间复杂度 ▶ 建 k 个元素的堆为O(K) ▶ 遍历剩余的 N-K 个元素的时间代价为O(N-K)假设运气很差每次遍历都入堆调整 ▶ 入堆调整删除堆顶元素和插入元素都为O(log2K) ▶ 所以时间复杂度为O(k (N-K)log2K)。当 N 远大于 K 时为O(N*log2K)这种解法更优。 ✨假如要找出最大的前 10 个数 ▶ 建立 10 个元素的小堆数据集合中前 10 个元素依次放入小堆此时的堆顶元素是堆中最小的元素也是堆里面第 10 个最小的元素 ▶ 然后把数据集合中剩下的元素与堆顶比较若大于堆顶则去掉堆顶再将其插入 ▶ 这样一来堆里面存放的就是数据集合中的前 10 个最大元素 此时小堆的堆顶元素也就是堆中的第 10 个最大的元素 ✨思考为什么找出最大的前10个数不能建大堆呢 如果你建的10个元素的大堆堆顶元素恰好是数据集合中最大的那个那第2大的数、第3大的数不就能找不到了。 三、完整代码和视图 以从1w个数里找出最大的前10个数为例 #include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int HPDatatype;
void Swap(HPDatatype* x, HPDatatype* y)
{HPDatatype temp 0;temp *x;*x *y;*y temp;
}void AdjustDown(HPDatatype* a,int n,int parent)
{// 左孩子int child parent * 2 1;// 防止越界while (child n){//小堆if (child 1 n 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 TopK(HPDatatype* a, int n, int k)
{HPDatatype* kminHeap (HPDatatype*)malloc(sizeof(HPDatatype) * k);assert(kminHeap);// 1. 建堆----用a中前k个元素建堆for (int i 0; i k; i){kminHeap[i] a[i];}// 建小堆for (int j ((n - 1) - 1) / 2; j 0; j--){// 从倒数第一个非叶子节点开始AdjustDown(kminHeap, k, j);}// 2. 将剩余n-k个元素依次与堆顶的元素交换比堆顶大交换for (int i k; i n; i){if (a[i] kminHeap[0]){kminHeap[0] a[i];//如果比堆顶大就替换AdjustDown(kminHeap, k, 0);//向下调整确保为堆}}for (int j 0; j k; j){printf(%d , kminHeap[j]);}printf(\n);free(kminHeap);
}int main()
{int n 10000;int* a (int*)malloc(sizeof(int) * n);srand(time(0));for (int i 0; i n; i){a[i] rand() % 1000000; //产生一个随机数数值均小于100万}a[5] 1000000 1;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;TopK(a, n, 10);return 0;
} 四、共勉 以下就是我对数据结构---堆排序的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对数据结构-------链式二叉树请持续关注我哦
