玩转堆排序以及Topk问题——【数据结构】

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

玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

W...Y的主页 😊

代码仓库分享  💕


目录

堆排序 

建堆

 建堆的时间复杂度

Topk问题


学习了二叉树以及堆,今天我们来学习一下什么是堆排序以及经典二叉树问题——topk问题。

在学习开始我们先来回顾一下上篇博客中我们提到的堆,在实现堆时我们要进行向上调整或向下调整来继续保存堆的特性。具体代码如下:

向上调整函数:

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向下调整函数:

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

这是在堆的删除以及插入中我们要用到的。

堆排序 

我们知道小堆就是其父节点的数小于等于子节点,而大堆就是父节点的数大于等于子节点的数。而根节点就是堆上最大或最小的数,在上篇博客中,我们实现了堆,并且完成了关于堆的插入、删除、取顶……一系列功能函数。我们只需要正确的使用,先取顶然后排序让其继续有堆的特性,再次重复这一个步骤,直到树为空树时我们就可以实现堆排序。

但是我们一般不会这样去使用堆排序,因为要实现堆排序接口太多,代码太复杂。而且一般常见的是直接给我们一长串数字让我们进行排序,如果要先一个个插入调整成堆,再进行排序时间复杂度也非常高。

那我们应该怎么办呢?

我们一般会先让整串数乱序放入数组,然后直接建堆,然后进行堆排序。

升序建大堆,降序建小堆。

那我们为什么要升序建大堆呢?建小堆不是更好吗?直接可以从中堆顶取出最小值。然后依次类推。这样是万万不能的,当取出最小值后,我们一般只能将数组中的其余数据往前挪动一位,但是挪动后就不是堆了关系全乱了,又得重新排列成堆继续取值,时间复杂度会高。

玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

如果我们升序建大堆的话,我们就可以使用我们实现堆中的删除思想进行。

玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

降序建小堆的原理也是删除思想,可以参考升序建大堆。玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

建堆

我们之前的方法是一个个插入然后向上调整,最后得到堆。但是如果遇到许多数据一起进行建堆,我们应该如何应对呢?

我们可以使用向下调整的方式建立堆,怎么建立呢?通过一组图片告诉大家:玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

所以我们找倒数第一个非叶子节点即可。我们又知道最后一个叶子节点的下标为(k-1),那我们就可以推出parent父节点的下标为(k-2)/2。然后依次往上走就可以将堆建好。

for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(minheap, k, i);
	}

上述代码即可建好堆。

那向上调整与向下调整哪个更好呢?我们下面来看一下它们的时间复杂度!!!

 建堆的时间复杂度

向下调整:

玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

向上调整:
玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

我们发现还是向下调整的时间复杂度低,这是为什么呢?
因为向下调整,当在底层时遇到的数据多但是调整次数少,而向上调整在底层的节点多调整的次数也多(更通俗的讲就是多对多、少对少)所以时间复杂度高。

所以我们一般使用向下调整会让程序优化!

当我们建好堆后,然后使用删除思想向下调整就可以完成堆排序:玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言 

Topk问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

一般情况下,我们先想到的就是暴力查找,在数据中找到需要的前k个数,但是时间复杂度非常高,第二个我们也可以将数据先进行排序qsort,然后再取前k个数内容。代码量会被优化,时间复杂度也会降低,但是也不是我们解决的最优办法。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

我们先在文件中生成10000个随机数:

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	const char* file = "data.txt";
	FILE* fp = fopen(file, "w");
	if (fp == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fp, "%d\n", x);
	}
	fclose(fp);
	PrintTopK(file,10);
}

然后再调用printtopk函数,传入文件名字与需要的k个数据。

读取文件中k个数据建成小堆,然后进入循环将剩下的数与根节点内容进行比较如果比根节点大就将根节点切换,然后向下调整继续形成小堆,继续循环直到文件读到末尾即可。 

void PrintTopK(const char* filename, int k)
{
	FILE* fp = fopen(filename, "r");
	if (fp == NULL)
	{
		perror("fopen error");
		return;
	}
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc perror");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(fp, "%d", &minheap[i]);
	}
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(minheap, k, i);
	}
	int x = 0;
	while (fscanf(fp, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
	fclose(fp);
}

我们在程序中使用的依旧是向下调整建堆。

在此程序中,我们随机数的范围为0~999999,运行结果如下玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

这就是我们随机生成的最大的前10个数据。

但是我们就会有疑问,万一数据不是最大的前10个呢该怎么办? 这里教大家一个测试方法:先确保运行过一次,然后屏蔽生成随机数写文件的一段程序,然后进入txt文件中。因为我们随机数范围为0~999999,所以我们在txt文件中生成比999999大的数,如果最后结果为自己改的数,则程序是正确的,反之程序就有问题需要修改。玩转堆排序以及Topk问题——【数据结构】,算法,数据结构,c语言

当我修改10个数后的运行结果全部是我修改的数据,说明我的程序没有问题。

最后在说明一下为什么要前k个最大元素要建小堆呢?

因为小堆可以找到树中最小的数,与文件中进行比较即可替换掉最小的数。如果使用大堆根节点为最大值,我们找到比根节点的大的数,这个数比堆中所有的数都大,我们找不出最大的k个内容,有可能将更小的数选中。

同理可得,要前k个最小元素要建大堆。 

以上就是堆的两个经典问题,如果博客中讲解有误,请及时与博主。

感谢大家观看,留下一键三连再走吧!!!谢谢❤️❤️ 文章来源地址https://www.toymoban.com/news/detail-727218.html

到了这里,关于玩转堆排序以及Topk问题——【数据结构】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【初阶数据结构】——堆排序和TopK问题

     ========================================================================= 个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏  ========================================================================= 接上篇二叉树和堆的引入 =========================================================================  目录 前言 建堆 插

    2024年02月07日
    浏览(42)
  • 数据结构:堆的应用(堆排序和topk问题)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 堆排序即是 先将数据建堆,再利用堆删除的思想来排序。 将待排序数组建堆 将堆顶数据与数组尾部数据交换 调整新的堆顶数据,使其保证堆的结构不变 重复2,3步直到堆中没有数据结束。 降序 建小堆 (父节点 小于

    2024年02月13日
    浏览(38)
  • 【数据结构之二叉树简介·顺序存储·应用:堆·堆排序·TOPK问题】

    ​ 🕺作者: 迷茫的启明星 😘欢迎关注:👍点赞🙌收藏✍️留言 🎃相关文章 【数据结构从0到1之树的初识】 【数据结构】带你学会二叉树的链式存储的前中后序遍历,遍历推导及利用队列实现二叉树的层次遍历。 🏇家人们,码字不易,你的👍点赞🙌收藏❤️关注对我

    2024年02月01日
    浏览(35)
  • 【数据结构】长篇详解堆,堆的向上/向下调整算法,堆排序及TopK问题

    堆就是将一组数据所有元素按完全二叉树的顺序存储方式存储在一个 一维数组 中,并满足树中 每一个父亲节点都要大于其子节点 称为 大堆 (树中 每一个父亲节点都要大于其子节点 称为 小堆 )。 性质 ①对于大堆(大根堆)来说,堆的顶部也就是数组首元素一定是最大的元素 ②

    2024年02月07日
    浏览(40)
  • 数据结构学习分享之堆的详解以及TopK问题

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:数据结构学习分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你了解更多数据结构的知识   🔝🔝 本章就给大家带来久违的堆的知识,如果你还不知道数的相关知识,或者什么是完全二叉树,请跳转 树的介绍, 本章的堆结

    2024年02月05日
    浏览(96)
  • 堆的实际应用(topk问题以及堆排序)

    目录 前言: 一:解决topk问题 二:堆排序 【1】第一种方法(很少用) 【2】第二种方法(很实用) 上一次我们进行了二叉树的初步介绍并实现了堆的基本功能,但堆的作用并不是存储数据, 它可以用来解决topk问题 ( 求一组数据较大或者较小的前k个 )以及 对数据进行排序 。 附上一

    2024年02月01日
    浏览(39)
  • 【数据结构】---TopK问题

    本文提供用建堆来解决TopK问题的一个思路 N个数中找出最大的或者最小的前k个 假设现从N个数中找最小的前k个 ①堆排序, 时间复杂度O(N*logN),这N个数排一下序,前k个数就是需要的 ②建堆N个数的小堆 ,HeapPop k-1 次,就选出来了,因为小堆最小的在堆顶,选出一次后,再删除

    2024年02月12日
    浏览(46)
  • 【数据结构】——解决topk问题

    前言:我们前面已经学习了小堆并且也实现了小堆,那么我们如果要从多个数据里选出最大的几个数据该怎么办呢,这节课我们就来解决这个问题。我们就用建小堆的方法来解决。 首先我们来看到这个方法的时间复杂度,我们先取前k个数据建立一个小堆,后面插入的数据依

    2024年02月04日
    浏览(40)
  • 【数据结构】【堆】 堆排,TOPK问题

    堆排序,就是先将数据构建成堆,根据需要构建大堆或者小堆。 如果要排降序,就构建小堆。 如果要排升序,就构建大堆。 我们 以降序为例 : 在构建好小堆后,堆顶的数据就是最小的。 我们将堆顶数据与最后一个数据进行交换,然后把堆的最后一个位置排除在外(即它不

    2024年02月07日
    浏览(35)
  • 【数据结构】堆的应用-----TopK问题

    目录 一、前言 二、Top-k问题   💦解法一:暴力排序 💦解法二:建立N个数的堆 💦解法三:建立K个数的堆(最优解) 三、完整代码和视图  四、共勉 在之前的文章中,已经详细的讲解了二叉树、堆、堆排序。那么关于堆还有一个比较有意思的题,就是TopK问题。 如果对堆

    2024年02月07日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包