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

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

 =========================================================================

个人主页

代码仓库

C语言专栏

初阶数据结构专栏

Linux专栏

 =========================================================================

接上篇二叉树和堆的引入

========================================================================= 

目录

前言

建堆

插入数据向上调整算法建堆

移动数据向上调整算法建堆

无序数组从H-1层向上移动的向下调整算法建堆

堆排序

TOP-K问题


前言

上篇文章详细讲解了堆,最后在执行完整代码后我们发现在删除堆中的数据时可以实现排序,当然这不是偶然,一切都是有迹可循的,今天就来讲解下用堆来实现排序,以及使用堆排序解决TopK问题。

建堆

插入数据向上调整算法建堆

上篇文章中我们就实现了这个步骤,在主函数中创建了个数组然后将数组中的每个数据使用插入函数和向上调整算法函数依次插入动态开辟的空间中,每插入一个数据作为孩子和父亲相比较,根据大小交换位置,最终实现大/小堆。

插入函数

void HPPush(HP* php, HPDatatype x)
{
	assert(php);
	
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDatatype* tmp = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	HPadjustUp(php->a, php->size-1);
}

进入函数首先判断空间大小是否足够 ,不够的话使用realloc库函数开辟空间,开辟不成功直接退出,开辟成功的话赋值和修改size和容量。 

向上调整函数和交换函数 

void HPadjustUp(HPDatatype* a, int child)
{
	//找到父亲
	int parent = (child - 1) / 2;
	//根为0  当和根交换后child为0
	while (child > 0)
	{
		//当child小时和父亲交换 建成小堆
		//当child大时和父亲交换 建成大堆
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

 进入向上调整函数根据我们上篇内容提供父亲和孩子之间下标的关系,依次向上调整根据我们的需要和父亲孩子的大小关系,用交换函数实现大/小堆。

​
void swap(HPDatatype* x, HPDatatype* y)
{
	HPDatatype tmp = *x;
	*x = *y;
	*y = tmp;
}

​

【初阶数据结构】——堆排序和TopK问题,数据结构挨打小记,数据结构,c语言,算法

为防止局部变量出交换函数作用域被销毁,这里我们使用指针交换。

这种方式的缺点

1.需要动态开辟空间,造成空间浪费。

2.需要完整的堆实现的代码,比较麻烦不是很推荐。

我们可以使用下面的方法对上面的函数进行优化。


移动数据向上调整算法建堆

根据我们这个方法的名字就可以判断我们这个方法是不需要动态开辟额外的空间,只需要使用数组下标通过向上调整算法函数来实现。

实现代码

	for (int i = 1; i < n; i++)
	{
		HPadjustUp(a, i);
	}

 这里我们将数组中的第一个数据作为一个堆通过下标的移动让后面的数字和前面的数字比较,也就相相当于前面的数字作为父亲后面的数字作为孩子,父亲和孩子使用向上调整函数进行调整实现堆。

【初阶数据结构】——堆排序和TopK问题,数据结构挨打小记,数据结构,c语言,算法

像这样经过多次的移动就形成我们的堆。  


无序数组从H-1层向上移动的向下调整算法建堆

【初阶数据结构】——堆排序和TopK问题,数据结构挨打小记,数据结构,c语言,算法

上篇文章我们介绍了向下移动的调整算法,但是这个算法有个前提就是除根外的左右子树都要是堆,但是我们这里给定一个无序数组先让这个数组模拟成堆,除根外左右子树有可能都不是堆,就无法实现向下调整算法,这样我们从倒数第一个非子叶结点开始向下调整也就是最后一个结点的父亲开始向下调整,我们直到数组在空间中是连续的,那我们从这个结点开始没向下调整依次,这个结点向前移动依次这样就将一个大堆分成各个小堆,完成向下调整了。

实现代码

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

【初阶数据结构】——堆排序和TopK问题,数据结构挨打小记,数据结构,c语言,算法

像这样经过多次的向下调整,最终就可以实现堆。 


堆排序

在实现堆排序之前我们先思考下升序和降序需要建什么堆?

我们这里直接给出答案:

升序:建大堆

降序:建小堆

问什么会是这样呢?

在上篇文章中堆的删除中,我们已经隐含的告诉大家了,如果我们要删除堆中的数据时直接向前移动数据会造成不是原有的大堆或者小堆,因此我们将根结点的数据和最后一个数据交换,两个子树依然是堆然后进行向下调整,size向前移动。我们不做删除这一步是不是就是排序!

【初阶数据结构】——堆排序和TopK问题,数据结构挨打小记,数据结构,c语言,算法

实现代码

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

TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void PrintTopK(const char* filename, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}

	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	// 前k个数建小堆
	for (int i = (k-2)/2; i >=0 ; --i)
	{
		AdjustDown(minheap, k, i);
	}


	// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
	int x = 0;
	while (fscanf(fout, "%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");

	free(minheap);
	fclose(fout);
}

// fprintf  fscanf

void CreateNDate()
{
	// 造数据
	int n = 10000000;
	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() + i) % 10000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

int main()
{
	//CreateNDate();
	PrintTopK("data.txt", 5);

	return 0;
}

文件操作知识忘了的话自己回顾下。

今天的内容到这里就结束了,感谢大家的观看!可以在评论区多多交流和探讨,指出我的错误!

下篇文章将讲解完全二叉树的实现!请大家敬请期待!!!文章来源地址https://www.toymoban.com/news/detail-723852.html

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

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

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

相关文章

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

    W...Y的主页 😊 代码仓库分享  💕 目录 堆排序  建堆  建堆的时间复杂度 Topk问题 学习了二叉树以及堆,今天我们来学习一下什么是堆排序以及经典二叉树问题——topk问题。 在学习开始我们先来回顾一下上篇博客中我们提到的堆,在实现堆时我们要进行向上调整或向下调

    2024年02月07日
    浏览(39)
  • 数据结构:堆的应用(堆排序和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问题

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

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

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

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

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

    2024年03月14日
    浏览(59)
  • 数据结构之树(Topk问题, 链式二叉树)

    取N个数中最大(小)的前k个值,N远大于k 这道题可以用堆的方法来解决,首先取这N个数的前k个值,用它们建堆 时间复杂度O(k) 之后将剩余的N-k个数据依次与堆顶数据进行比较,如果比堆顶数据大,则将堆顶数据覆盖后向下调整 时间复杂度(N-k)*log(N) 总共的时间复杂度为O(N*log(N)) 用数组

    2024年03月15日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包