【数据结构】堆排序与TopK问题

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

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

 1.堆的概念和结构

2.堆的实现

2.1向上调整算法

2.2向下调整算法

2.3堆的创建

2.4建堆时间复杂度

2.5堆的插入

2.6堆的删除

2.7堆的代码实现

3.堆的应用

3.1堆排序

3.2TopK问题


前言

本篇文章博主主要围绕堆这一数据结构展开,内容包括两种建堆方式,两种建堆方式的时间复杂度分析,最后引入堆的应用:堆排序和TopK问题,希望大家多多点赞收藏支持🔥


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================文章来源地址https://www.toymoban.com/news/detail-725181.html

GITEE相关代码:🌟fanfei_c的仓库🌟

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


 1.堆的概念和结构

堆的逻辑结构是完全二叉树。

逻辑结构的视角观察:

在大根堆中,双亲节点大于孩子节点;

在小根堆中,双亲节点小于孩子节点。

堆的存储结构是一维数组。 

存储结构的视角观察(设数组K):

在小根堆中:K[i]<=K[2*i+1] && K[i]<=K[2*i+2];

在大根堆中:K[i]>=K[2*i+1] && K[i]>=K[2*i+2];

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记


2.堆的实现

2.1向上调整算法

向上调整算法的前提是祖先是堆。

以小堆为例:

1.给定向上调整的起点(孩子节点下标),根据起点下标计算双亲节点下标。

孩子节点与双亲结点间的下标关系:

child=parent*2+1 || child=parent*2+2;

parent=(child-1)/2;

2.比较孩子节点与双亲节点数值大小,若孩子节点小于双亲节点,则交换两者,并将孩子节点的下标更新为之前的双亲节点下标,根据最新的孩子节点下标重新计算双亲节点下标,重复这一过程直到孩子节点为根节点。

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记

代码实现: 

//向上调整
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 = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

2.2向下调整算法

向下调整算法的前提是左右子树是堆。

以小堆为例:

1.给定向下调整的起点(双亲节点下标)和节点总数,根据起点下标计算孩子节点下标。

注意:向下调整时,若有两个孩子节点,则需要确保调整的是较小的孩子节点。

2.比较孩子节点与双亲节点数值大小,若孩子节点小于双亲节点,则交换两者,并将双亲节点的下标更新为之前的孩子节点下标,根据最新的双亲节点下标重新计算孩子节点下标,重复这一过程直到孩子节点超出节点总数。

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记

代码实现:

//向下调整
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 = child + 1;
		}
		if (a[child] < a[parent])//建小堆
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.3堆的创建

堆的创建既可以使用向上调整算法,也可以使用向下调整算法。

1.向上调整算法建堆

由于向上调整算法的前提是祖先是堆,所以我们需要从第二个节点开始向上调整(即根节点的下一个)。

代码实现:

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

2.向下调整算法建堆

 由于向下调整算法的前提是左右子树是堆,所以我们需要从倒数第一个非叶子节点向下调整。

已知节点总数为n,那么倒数第一个节点的下标即为n-1,该节点的双亲节点下标即为(n-1-1)/2,该双亲节点就是倒数第一个非叶子节点(因为堆是完全二叉树)

代码实现:

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

2.4建堆时间复杂度

假设树的高度为h。

1.向上调整建堆时间复杂度

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记

 则需要移动节点总的移动步数为:

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记

即向上调整建堆的时间复杂度为O(N*log₂N)。 


2.向下调整建堆时间复杂度

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记

则需要移动节点总的移动步数为:

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记

即向下调整建堆的时间复杂度为O(N)。 


2.5堆的插入

首先尾插到该数组,再向上调整即可。

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记


2.6堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。

【数据结构】堆排序与TopK问题,数据结构,c语言,开发语言,数据结构,学习,笔记


2.7堆的代码实现

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (hp->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	hp->capacity = hp->size = n;

	memcpy(hp->a, a, sizeof(HPDataType) * n);
	for (int i = 1; i < n; i++)
	{
		Adjustup(hp->a, i);
	}
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	assert(hp->a);
	//1.检查容量 
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) *newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}

	hp->a[hp->size] = x;
	hp->size++;
	
	Adjustup(hp->a, hp->size-1);
}

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	--hp->size;

	Adjustdown(hp->a, hp->size, 0);
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->a);
	return hp->a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

3.堆的应用

3.1堆排序

方法1:

首先,我们当然可以利用已经堆这一数据结构进行输出有序的数据。

以升序为例:

首先构建小堆,然后输出堆顶元素,再Pop,再向下调整,循环执行此步骤直到堆空。

代码实现:

void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}
	
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		//printf("%d ", HeapTop(&hp));
		a[i++] = HeapTop(&hp);
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}

但这样有很明显的缺点

1.需要堆这样一个数据结构,构建麻烦;

2.空间复杂度的消耗。


方法2: 

以升序为例:

首先构建大堆(推荐使用向下调整),此时堆顶元素一定为最大值,然后将堆顶元素与最后一个节点交换,此时最大值就放到了整个数组的最后面,然后除了最后一个值以外,其他的数据再向下调整,调整完成后堆顶元素为次大值,再与数组倒数第二个位置的值交换,这样依此往复就得到了升序数组。

注意:

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

代码实现:

void HeapSort(int* a, int n)
{
	// 向上调整建堆 (大堆)or  (小堆)
	// O(N*logN)
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/

	// 向下调整建堆
	// O(N)
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

3.2TopK问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

最佳的方式就是用堆来解决,基本思路如下:

1.用数据集合中前K个元素来建堆

  • 前k个最大的元素,则建小堆
  • 前k个最小的元素,则建大堆

2.用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

 首先可以写一段生成随机数字的程序,并将这些数字写入到文件中。

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);
}

根据上面分析的思路完成代码。

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");

	fclose(fout);
}

堆处理大量数据的速度非常快,我们都知道对数的特性,所以堆处理大量数据的能力非常强。在遇到TopK问题或者大量数据排序时,可以考虑使用堆排序。

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

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

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

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

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

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

相关文章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    2024年03月15日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包