解密堆排序与TopK问题

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

📙作者简介: 清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。

📘相关专栏:C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。

欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正!

✨每一次努力都是一种收获,每一次坚持都是一种成长✨       

解密堆排序与TopK问题,数据结构入门指南,算法,数据结构,经验分享,c语言

目录

 前言

1. 堆排序

1.1 时间复杂度

 1.1.1 向上调整(建堆)

 1.1.2 向下调整 (建堆)

 1. 2 排序实现

2. Topk问题

 2.1 什么是Topk问题

 2.2 Topk问题的解决

 2.2.1 造数据

 2.2.2 Topk的实现

总结


 前言

        在二叉树的存储结构中提到堆可以进行排序,也就是今天的主题堆排序,堆的排序还可以解决Topk问题,今天我就向大家解密什么是堆排序和Topk问题,它们的原理又是什么。


1. 堆排序

        堆是一种特殊的完全二叉树,堆排序是一种基于二叉堆数据结构的排序算法。堆排序是利用堆的特性来对堆中的数据进行排序,那么问题来了:

        如果我们要排升序,需要建大堆还是小堆?绝大多数人的第一反应是建小堆,但建小堆真的可以将数据进行升序排列吗?

         我们看下边这棵树,如果是小堆,那如何去找第二小的数?我们需要根据堆的特性,对数据进行调整位置,来达到排序的问题。

解密堆排序与TopK问题,数据结构入门指南,算法,数据结构,经验分享,c语言

 显然小堆是无法做到的,要想排升序就必须要建大堆。大堆排升序思路如下:

解密堆排序与TopK问题,数据结构入门指南,算法,数据结构,经验分享,c语言

         大堆的根是整棵树中最大的值,那我们就可以让根和最后一个节点进行交换(70和10进行交换),然后将剩下的节点进行调整(不包含70),调整后的根就是第二大的数。

解密堆排序与TopK问题,数据结构入门指南,算法,数据结构,经验分享,c语言

 然后继续上述操作,将56和15进行交换,然后再进行调整,以此类推,最终数据就会被排为升序。

总结来说,堆排序主要有两大步骤:

  • 建堆
  • 调整数据

 建堆,我们可以选择向上调整或者向下调整。

调整数据部分,必须为向下调整。

1.1 时间复杂度

        说到了排序,那就必须要谈一谈它的性能如何?也就是它的时间复杂度。

 1.1.1 向上调整(建堆)

         向上调整的思路是从孩子(叶子节点)开始调整,最坏调整到根节点,调整情况如下:解密堆排序与TopK问题,数据结构入门指南,算法,数据结构,经验分享,c语言

         每层的数据个数 * 每层调整次数=一层最多执行的次数。那要求的是总共需要执行的次数就是每层的执行次数之和。我们设总的执行次数为T(h)。

所以:T(h)=2^1*1 + 2^2*2 + 2^3*3 … +2^(h-2)*(h-2) + 2^(h-1)*(h-1)  ;

计算部分为高中数学的知识,私下可以验算一下,最终的结果为:T(h)=(h-2)* 2^h+2,

将h代换成N(节点个数),N=2^h-1,h=log(N+1),

T(N)=( log (N+1) - 2 )  *  (N+1) + 2(此处的log以2为底),最终就约等于N*log N

所以向上调整建堆的时间复杂度就是O(N*log N)

 1.1.2 向下调整 (建堆)

         向下调整是从根节点开始,最坏调整到叶子节点,调整情况如下:

解密堆排序与TopK问题,数据结构入门指南,算法,数据结构,经验分享,c语言

         这里我们可以看出,向下调整的时间复杂度和向上调整不同,我们设总的执行次数为T(h)。

T(h)=2^0*(h-1) + 2^1*(h-2) + 2^2*(h-3) … +2^(h-3)*2 + 2^(h-2)*1 ; 

最终的结果为:T(h)=2^h-h-1 ;

将h代换成N(节点个数),N=2^h-1,h=log(N+1);

T(N)=N-log(N+1);最终就约等于N;

所以向下调整建堆的时间复杂度就是O(N); 

 注意这里要区分清,是建堆操作还是调整操作,单一的执行一次调整,向上调整和向下调整的时间复杂度都是log N。

 1. 2 排序实现

void HeapSort(int* arr, int n)
{
	//向上调整建堆,时间复杂度O(N*log N)
	for (int i = 1; i < n; i++)
	{
		AdjustUp(arr, i);
	}
	//向下调整建堆,时间复杂度O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}

}

注意:

        向上调整时我们需要保证上方的数据结构是堆,所以这里我们从头开始读入数据,读一个数据就调整一次。这样就可以确保每次调整时,其他的数据都是堆结构。

        向下调整的前提是左右子树都为堆结构,所以我们需要保证左右子树都为堆,这里我们传参时不能从头开始,要从倒数第一个的非叶子节点开始(最后一个父节点),从后向前进行调整建堆。

 向上调整

这里我们建的是大堆 。

void AdjustUp(int* arr,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[parent] < arr[child])//建大堆排升序
		{
			swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向下调整

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

2. Topk问题

 2.1 什么是Topk问题

        Top-K问题是指从一组元素中找出前K个最大(或最小)的元素。这个问题在数据处理和算法设计中经常遇到,常见的应用场景包括搜索引擎中的搜索结果排序、推荐系统中的物品推荐、数据分析中的数据筛选等。

Topk问题,我们就可以使用堆来解决,对于Top-K问题,一般有两种情况:

  • 找出前K个最大的元素:可以使用最小堆来解决,维护一个大小为K的最小堆,遍历所有元素,将每个元素与堆顶元素进行比较,如果大于堆顶元素,则将堆顶元素替换为当前元素,并进行堆调整。最终堆中的元素即为前K个最大的元素。
  • 找出前K个最小的元素:可以使用最大堆来解决,维护一个大小为K的最大堆,遍历所有元素,将每个元素与堆顶元素进行比较,如果小于堆顶元素,则将堆顶元素替换为当前元素,并进行堆调整。最终堆中的元素即为前K个最小的元素。

        通过解决Top-K问题,可以快速获取数据中的重要信息,提高算法的效率和性能。

 2.2 Topk问题的解决

 2.2.1 造数据

         为了模拟实现Topk问题在现实生活中的应用,所以在测试时我们需要采用大量的数据进行测试,我们自己手动输入是远远不够的,所以我们这里采用strand函数进行造数据。

void CreateNDate()
{
	// 造数据
	int n = 1000000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = rand() % 10000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

        这里我们造了100万个数据。将数据默认放到了一个data.txt的文件中。我们先运行一下这个函数接口,然后打开在程序的当前路径下找到data.txt文件,将任意的k个数据手动修改(可以前边加4个9,增加辨识度)确保判断找出的数据为前k的最值。这里我们选择找出前k个最大的数据。

注意造完数据后要将造数据接口注释掉,修改数据后记得将文件保存

 2.2.2 Topk的实现

         根据上述的思路,要想找到前k个最大的数据,就需要建小堆,这样堆顶就是堆中最小的数据,比堆顶大就置为根入堆,最后将所有数据遍历一遍之后,留在堆里的数据就是前k个最大的数据。

这里我们依然需要前边的调整代码。具体代码如下:

void PrintTopK(const char* filename,int k) {
    //打开文件,读取数据
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
    
    //建堆
	int* setHeap = (int*)malloc(sizeof(int) * k);
	if (setHeap == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
    //读取前k个数据建堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &setHeap[i]);
	}
	for (int i = 0; i < k; i++)
	{
		AdjustUp(setHeap, k);
	}
    
    //遍历入堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
        
		if (x > setHeap[0])    //比堆顶大就入堆
		{
			setHeap[0] = x;
			AdjustDown(setHeap, k, 0);    //入堆之后向下调整
		}
	}
	
	for (int i = 0; i < k; i++)
	{
		printf("%d ", setHeap[i]);
	}
	printf("\n");

	fclose(fout);
}

建小堆调整代码

void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[parent] > arr[child])//建大堆排升序
		{
			swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] < arr[child])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

main接口:

int main()
{
	//CreateNDate();
	PrintTopK("data.txt", 7);
	return 0;
}

总结

        本篇博客主要介绍了堆排序算法及其在解决TopK问题中的应用。通过对堆排序的原理和实现步骤的详细讲解,我们可以更好地理解和掌握这一经典的排序算法。同时,通过解决TopK问题的实例,我们也可以看到堆排序在实际应用中的价值和优势。希望本篇博客能够为你提供一些有用的思考和启发。最后,感谢阅读!文章来源地址https://www.toymoban.com/news/detail-732440.html

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

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

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

相关文章

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

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

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

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

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

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

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

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

    2024年02月01日
    浏览(37)
  • 【数据结构】---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问题

    📙 作者简介:  清水加冰,目前大二在读,正在学习C/C++、Python、操作系统、数据库等。 📘 相关专栏: C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正! ✨每一次努力都

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

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

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

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

    2024年02月07日
    浏览(48)
  • 数据结构——堆的应用 Topk问题

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月14日
    浏览(59)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包