虫子 TopK 基本算法
【摘要】 Topk 1000个数中找到最大的前十个 方式1: 方式2: ==方式3:== Topk打印函数TopkPrint 没有修改的接口见 算法给小码农堆魂器–铁血柔情 改掉的接口 向上调整函数 向下调整函数 然后在Heap.h文件中加入 Topk在n个数中找出最大的前K个 or 在n个数中找出最小的前K个(n>K) 1000个数中找到最大的前十个 方式1:先排降序,前十个就是最大的。时间复杂...
Topk
在n个数中找出最大的前K个 or 在n个数中找出最小的前K个
(n>K)
1000个数中找到最大的前十个
方式1:
先排降序,前十个就是最大的。时间复杂度O(N*log~2~N)
方式2:
N个数依次插入大堆,PopK次,每次取堆顶的数据就是最大的前K个。==时间复杂度O(N+log~2~N)==(下篇证明)
==方式3:==
假设N非常大,N是10亿,内存中存不下这些数,他们存在文件中,k是100。那么方式1与方式2就都不可以用了。==时间复杂度 O(K+(N-K)log~2~K)==
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
【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)