目录
前言:
一、Top-K问题描述:
二、不同解决思路实现:
①.排序法:
②.直接建堆法:
③.K堆法
总结:
前言:
上篇文章我们学习了二叉树的顺序存储结构,并且对于实际使用中所常用的顺序存储结构——堆的各个接口进行实现。这篇文章我们将对堆的实际应用进行更加深入的研究。
一、Top-K问题描述:
Top-K问题,就是求数据结合前K个最大的元素或者最小的元素,一般情况下数据量较大。比如:美团上的附近美食排行榜、年纪成绩排行榜等等。
而对于Top-K问题,我们能想到的有三种不同的思路去解决。首先最简单直接的方式就是排序。但是如果需要处理的数据量非常大,排序就不太可取了。而另外两种方法就是使用堆:
- 用数据集合中前K个元素来建堆,若要取前K个最大的元素,则建小堆;若要取前K个最小的的元素,则建大堆。
- 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素,最终堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
二、不同解决思路实现:
①.排序法:
排序法的思路很好理解,就是将所有的数据进行排序,再根据需求取值即可。过程中使用的排序方法就是向下调整,时间复杂度是O(nlogn):
//排序法:
Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void HeapSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
Adujustup(a, i);
}
while ((n-1) > 0)
{
Swap(&a[0], &a[n - 1]);
n--;
Adujustdown(a, n-1, 0);
}
}
这种方法就相当于遍历所有的数据进行比较排序,因此会将会造成大量的内存消耗和使用,存在着较大的弊端。
②.直接建堆法:
直接建堆法的作用原理为:建立一个大堆(时间复杂度O(logn)),然后取出堆顶元素并将其删除,然后调整堆,重复这个步骤K次。
void HeapSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
Adujustup(a, i);
}
for(int i=0;i<k;i++)
{
printf("%d",HeapTop(a));
HeapPop(a);
}
虽然这种算法有了一定程度的改进,但是仍然没有改变再内存中进行操作的本质,其操作方式仍然会造成大量内存的占用和消耗。
③.K堆法
由于上述两种方法都是当n很大时,所占用的内存将会非常大,例如我们假设n为100亿,此时便有:1G=1024Mb=1024*1024Kb=1024*1024*1024Byte,需要使用内存将达到10byte。
于是我们就采用另外一种建堆方式——K堆法:建一个大小为K的小堆。
为什么时小堆呢?
因为小堆的堆顶是K的元素中最小的,而我每次只需要跟堆顶比较然后淘汰K个元素中最
小的一个,最后N-K比较完之后这K个元素就是TopK了。文章来源:https://www.toymoban.com/news/detail-567066.html
void TestTopk(HP* p, int k)
{
int* arr = (int*)malloc(sizeof(int) * k);
int n = p->size;
for (int i = 1; i < n; i++)
{
SAdujustup(p->a, i);
}
for (int i = 0; i < k; i++)
{
arr[i] = p->a[0];
p->a[0] = p->a[p->size - 1];
p->size--;
n = p->size;
for (int i = 1; i < n; i++)
{
SAdujustup(p->a, i);
}
}
for (int i = 1; i < k; i++)
{
SAdujustup(arr, i);
}
for (int i = 0; i < k; i++)
{
printf("%d ", arr[i]);
}
}
总结:
到这里,我们今天关于Topk问题的研究就全部结束了,难度不大,最主要是结合具体情况,选择最合适的方法建堆。文章来源地址https://www.toymoban.com/news/detail-567066.html
到了这里,关于【数据结构】堆的应用——Top-K的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!