【数据结构】堆的应用——Top-K

这篇具有很好参考价值的文章主要介绍了【数据结构】堆的应用——Top-K。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言:

一、Top-K问题描述:

二、不同解决思路实现:

①.排序法:

②.直接建堆法:

③.K堆法

总结:

前言:

        上篇文章我们学习了二叉树的顺序存储结构,并且对于实际使用中所常用的顺序存储结构——堆的各个接口进行实现。这篇文章我们将对堆的实际应用进行更加深入的研究。

一、Top-K问题描述:

        Top-K问题,就是求数据结合前K个最大的元素或者最小的元素,一般情况下数据量较大。比如:美团上的附近美食排行榜、年纪成绩排行榜等等。

       而对于Top-K问题,我们能想到的有三种不同的思路去解决。首先最简单直接的方式就是排序。但是如果需要处理的数据量非常大,排序就不太可取了。而另外两种方法就是使用堆:

  1. 用数据集合中前K个元素来建堆,若要取前K个最大的元素,则建小堆;若要取前K个最小的的元素,则建大堆
  2. 用剩余的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了。

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】堆的实现,堆排序以及TOP-K问题

    目录 1.堆的概念及结构 2.堆的实现 2.1初始化堆 2.2销毁堆 2.3取堆顶元素 2.4返回堆的大小 2.5判断是否为空 2.6打印堆 2.7插入元素 2.8堆的向上调整 2.9弹出元素 2.10堆的向下调整 3. 建堆时间复杂度 4. 堆的应用 4.1 堆排序 4.2 TOP-K问题 堆是一种数据结构,它是由一组元素组成的,并

    2024年02月12日
    浏览(52)
  • 【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题

    目录 堆的概念及结构 ​编辑 堆的实现  实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据  交换 堆的插入(插入最后) 向上调整(这次用的是小堆) 堆的删除(删除根) 向下调整(这次用的小堆) 堆排序 TOP-K问题 如果有一个关键码的集合 K = { , , , …

    2024年02月05日
    浏览(54)
  • 数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K

            前言          逆水行舟,不进则退!!!                目录        认识堆        堆的创建         1,向下调整的方法建立堆         2,以向下调整的方式建立小根堆         3,向上调整的方式建堆        堆的插入        堆的删除              

    2024年02月04日
    浏览(56)
  • 堆的应用:Top-K问题

    朋友们、伙计们,我们又见面了,本期来给大家解读一下堆的应用--Top-K问题的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目

    2024年02月07日
    浏览(43)
  • 数据结构 | TOP-K问题

    TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。 就是从N个数里面找最大前K个(N远大于K) 思路一: N个数插入到堆里面,PopK次 时间复杂度是 O(N*logN) + K*logN == O(N*logN) N很大很大,假设N是100亿,K是10 100亿个整数大概需要40G左右 所以

    2024年02月05日
    浏览(41)
  • 数据结构与算法:堆排序和TOP-K问题

    朋友们大家好,本节内容来到堆的应用:堆排序和topk问题 我们在c语言中已经见到过几种排序,冒泡排序,快速排序(qsort) 冒泡排序的时间复杂度为O(N 2 ),空间复杂度为O(1);qsort排序的时间复杂度为 O(nlogn),空间复杂度为O(logn),而今天所讲到的堆排序在时间与空间复杂度上相

    2024年03月08日
    浏览(62)
  • 【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:堆排序+TOP-K问题 送给各位💌:日落跌入昭昭星野 人间忽晚 山河以秋 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面

    2024年02月06日
    浏览(47)
  • 数据结构之堆排序以及Top-k问题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.堆排序 2.1降序排序 2.2时间复杂度 3.Top-k问题 4.总结         在上一篇文

    2024年02月05日
    浏览(43)
  • 【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​ 目录 堆排序 第一种  ​编辑 第二种  TOP-K问题 建堆的时间复杂度 向下调整建堆的时间复杂度:  向上调整建堆的时间

    2024年01月21日
    浏览(61)
  • 【数据结构】—堆排序以及TOP-K问题究极详解(含C语言实现)

                                            食用指南:本文在有C基础的情况下食用更佳                                          🔥 这就不得不推荐此专栏了: C语言                                        ♈️ 今日夜电波: ルミネセンス—今泉愛夏      

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包