【数据结构】建堆算法复杂度分析及TOP-K问题
【数据结构】建堆算法复杂度分析及TOP-K问题
🔥个人主页:大白的编程日记
🔥专栏:数据结构
前言
哈喽,各位小伙伴大家好!上期我们讲了堆排序和建堆算法。今天我们就来分析一下他们的时间复杂度。话不多说,咱们进入正题。向大厂冲锋!
一.复杂度分析
我们都知道堆是一个完全二叉树。那他的高度h和节点数量N有什么关系呢?
那我们再来对比一下满二叉树和完全二叉树的高度h.
我们用大O渐进表示法看的话他们两个的高度h都可以认为是logN的量级
所以我们的堆的上下调整可以认为是logN,也就是高度次。
因为堆是完全二叉树,而满二叉树也是完全二叉树,所以为了方便证明
我们使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个结点不影响最终结果):
1.1向下建堆复杂度
我们先分别算出第一层到h-1层的节点个数和该层节点的调整次数
然后再推出总的调整次数。
- 推导
1.2向上建堆复杂度
我们先分别算出第2层到h层的节点个数和该层节点的调整次数
然后再推出总的调整次数。
- 推导
所以向下建堆的时间复杂度是O(N),向上建堆的复杂度是O(N*logN).
所以以后我们都尽量使用向下调整建堆。因为他的效率更高。
1.3堆排序复杂度
现在我们来看一下我们堆排序的时间复杂度是多少呢?
- 推导
堆排序的复杂度是O(N*logN).
二.TOP-K问题
2.1思路分析
我们的堆除了可以用来排序还可以用来解决经典的TOP-K问题。
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
- 方法一
我们很容易想到直接排序然后取出前K个即可。
但是这个方法有个致命缺陷。
如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
我们发现这个方法在数据量太大的时候并不适用。
那有什么其他好的方法吗? - 方法二
最佳的方式就是用堆来解决,基本思路如下:
1 .用数据集合中前K个元素来建堆
前k个最大的元素,则建K个数的小堆
前k个最小的元素,则建K个数的大堆
2 . 用剩余的N-K个元素依次与堆顶元素来比较,
如果比堆顶元素还要大或小(小堆大 大堆小)则替换堆顶元素,然后向下调整重新建堆。
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
为什么呢?
- 证明
我们通过N-K次比较就可以筛选出N-K个不满足最大前K个数的数
剩下在堆的数就是最大的前K个。 - 疑问
我们用反证法可以得知这种情况不存在。
2.2代码实现
- 生成数据函数
我们先用srand生成不同的种子防止生成的随机数是伪随机数。
然后fopen打开文件。循环生成随机数然后写入文件即可。最后关闭文件。
void CreatData()
{
int n = 100000;//生成10万个数据
srand(time(0));//生成不同的种子
FILE* pf = fopen("test.txt", "w");//打开文件
for (int i = 0; i < n; i++)
{
int x = rand() % 100001+i;//生成随机数
fprintf(pf, "%d\n", x);//写数据
}
fclose(pf);//关闭文件
pf = NULL;
}
这样10万个数据就生成好了。
- 比较函数
我们先接收k。然后开好k个数是堆空间。
然后从文件读取前k个数并填充到堆里面。然后建堆
然后继续读取文件里的数据直到文件末尾(返回EOF)
然后当数据大于堆顶元素是在进堆,然后重新调整建堆即可。
void test()
{
int k;
printf("请输入前K个数:");
scanf("%d", &k);
int* a = (int*)malloc(sizeof(int) * k);//开空间建堆
FILE* pf = fopen("test.txt", "r");
for (int i = 0; i < k; i++)
{
fscanf(pf, "%d", &a[i]);
}//填充数据
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, k, i);
}//建小堆
int x;
while (fscanf(pf, "%d", &x) !=EOF)
{
if (x > a[0])
{
a[0] = x;
AdjustDown(a, k, 0);
}
}//对比
for (int i = 0; i < k; i++)
{
printf("%d ", a[i]);
}//打印
}
- 检验
那我们如何确保这10个数一定是最大的呢?万一我们的算法写错不是最大的前10个数怎么办?
那我们就可以在不同的地方在一些k标点。
也就是K个很大的数,确保他们是最大的前K个。
然后只需要看结果是不是这k个数即可。
大家发现结果就是我们手动给的这10个数。说明我们的程序时没问题的。
后言
这就是建堆算法复杂度分析及TOP-K问题。这里涉及到许多数学知识。大家可以多看几遍证明图。今天就分享到这里。感谢大佬们垂阅!咱们下期见!拜拜~
原文地址:https://blog.csdn.net/2301_81670477/article/details/140644574
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!