数据结构之堆的应用

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

在我们学习了堆之后我们知道,无论是大堆还是小堆,堆顶的元素要么最大,要么最小。

对于堆插入的时间复杂度为O(logn)也就是向上调整算法的复杂度,删除一个堆中的元素为O(logn),堆在我们日常生活中还是常用到的。

目录

1.top k问题(优质筛选问题)

2.堆排序

1.向上调整建堆

建小堆-----最后排序为降序

建大堆------最后排序为升序 

2.向下调整建堆

建小堆--排序结果为降序

建大堆---排序结果为升序

向上与向下比较


1.top k问题(优质筛选问题)

什么是top k问题?即求数据结合中前k个最大元素或最小元素,一般情况下数据量较大。

假设N是100万,k是100,求100 万中的前10个最大数,当数足够大,排序已经无法实现了,空间太大,无法内存中开辟,在磁盘上开辟(但磁盘中无法建堆),而且磁盘运行速度很慢。

如:求得大量数字中的前k个大或前k个小的数,普通的算法时间复杂度较高,效率较慢,数量太大,无法寻找。利用堆的特性,算法效率高,面对数量大的数据也适用。

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

前k个最大元素  建大堆

前k个最小元素  建小堆

数据结构之堆的应用

 我们这里设置随机数10个,这里你可以改变,越大越能体现堆的功能,找出其中的最大五个,

思路就是先读取五个数进入数组里,之后再从第k+1个数开始与堆顶比较,比堆顶大就替换,每一次都要向下调整,确保是一个小堆,到最后最大的五个数就是小堆的五个数,第一个是五个里最小的。

#include<stdlib.h> 
#include<stdio.h>
#include<time.h>
void Adjustdown1(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if ((child + 1 < size) && a[child + 1] < a[child])//若右孩子存在且小于左孩子
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			//交换
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}
void creatnDATA()
{
	int n = 10;
	srand(time(NULL));
	const char* file = "data.txt";
	FILE* fp = fopen(file, "w");
	if (fp == NULL)
	{
		perror("fopen fail");
		return;
	}
	for (size_t i = 0; i < n; i++)
	{
		int x = rand() % 100000;
		fprintf(fp, "%d\n", x);
	}
	fclose(fp);

}
void printtopk(int k)
{
	const char* file = "data.txt";
	FILE* fp = fopen(file, "r");
	if (fp == NULL)
	{
		perror("fopen fail");
		return;
	}
	
	int* kminheap = (int*)malloc(sizeof(int) * k);

	//从文件中读k个数
	for (size_t i = 0; i < k; i++)
	{
		fscanf(fp, "%d", &kminheap[i]);
	}
	//建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown1(kminheap, k, i);
	}
	int val = 0;
	//比较 ,如果比堆顶大,则需要交换,之后再向下调整。
	while (!feof(fp))
	{
		//从第k+1个数处再开始读
		fscanf(fp, "%d", &val);
		//val用来存放读的数 
		if (val > kminheap[0])
		{
			 kminheap[0]=val;
			Adjustdown1(kminheap, k, 0);
		}
		
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");

}
int main()
{
	creatnDATA();
	printtopk(5);
	return 0;
}

2.堆排序

正常的思维,所谓对堆排序就是用堆这个数据结构来实现排序,思路也很简单,取堆头存入数组,向下调整,在出堆,循环往复。

如下,在有堆的前提,我们可以实现堆排序:

//前提有堆的实现
void heapsort(int *a,int n)
{
	HP f;
	Heapinit(&f);
	for (int i = 0; i < n; i++)
	{
		Heappush(&f, a[i]);
	}
      int i = 0;
	while (!HeapEmpty(&f))
	{
		//进行排序
		int top = HeapTop(&f);
		a[i++] = top;
		Heappop(&f);
		
	}

}
int main()
{
	int a[] = {10,6,9,3,5,7,65};
	heapsort(a,sizeof(a)/sizeof(int));
	for (int i=0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}

}

但我们也会发现其空间复杂度较高,需要拷贝数据,虽然这个堆排序效率还行,但是我们又看到想要以这种方法实现我们还的需要实现堆的所有操作!!!!这太麻烦了,那这种排序又有谁会用呢?

实则不然,真正的堆排序是利用堆的思路,我们是把传进来这个数组直接建堆,省去一部分操作,提高效率。因此建堆又有两种方式:

1.向上调整建堆

给出排序的数组,以此来建堆,根据堆的结构  

建小堆-----最后排序为降序

数据结构之堆的应用

void Adjustup1(HPDATAtype* a, int child)
{
	//根据孩子找父亲
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			HPDATAtype p = a[child];
			a[child] = a[parent];
			a[parent] = p;

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}

	}
}
void Adjustdown1(HPDATAtype* a, int size,int parent)
{
	int child =parent * 2 +1;
	while (child<size)
	{
		if ((child+1<size)&&a[child + 1] <a[child])//若右孩子存在且小于左孩子
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			//交换
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}else
		{
			break;
		}
	}

}
void heapsort1(int* a, int n)
{
	//向上调整建堆
	//从第一个元素开始就向上调整,保证前面都是堆结构,建小堆
	for (int i = 0; i < n; i++)
	{
		Adjustup1(a, i);
	}
	//在调整  ,选出一个个次小的数
	int end = n - 1;
	while (end > 0)
	{
		//把最小的数据交换到最后一个位置
		int tmp = a[0];
		a[0] = a[end];
		a[end] = tmp;
	Adjustdown1(a, end, 0);
	--end;
	}
}

建大堆------最后排序为升序 

数据结构之堆的应用

void Adjustup2(HPDATAtype*a, int child)
{
	//根据孩子找父亲
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if ( a[child]>a[parent])
		{
		  HPDATAtype p = a[child];
		  a [child] = a[parent];
		  a[parent]=p;

		  child = parent;
		  parent = (child - 1) / 2;
		}
		else 
		{
			break;
		}
		
	}
}
void Adjustdown2(HPDATAtype* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if ((child + 1 < size) && a[child + 1] > a[child])//若右孩子存在且小于左孩子
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			//交换
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}
void heapsort2(int* a, int n)
{
	//向上调整建堆
	//从第一个元素开始就向上调整,保证前面都是堆结构,建大堆
	for (int i = 0; i < n; i++)
	{
		Adjustup2(a, i);
	}
	//在调整  ,选出一个个次小的数
	int end = n - 1;
	while (end > 0)
	{
		//把最小的数据交换到最后一个位置
		int tmp = a[0];
		a[0] = a[end];
		a[end] = tmp;
		Adjustdown2(a, end, 0);
		--end;
	}
}

利用向上调整算法建堆,时间复杂度O(N*logN),这里是以2为底N的对数。

2.向下调整建堆

建堆与向上调整建堆是相反的,向下调整建堆,从数组后面开始调整,也就是从二叉树后面开始从前调整,知道符合堆的特性。

向下调整建堆也分建大堆还是小堆,根据你设计向下调整算法时,取决于条件-孩子大与父亲还是父亲大于孩子。

这里建小堆,调整数组是下标从中间开始的。

建小堆--排序结果为降序

void Adjustdown1(HPDATAtype* a, int size,int parent)
{
	int child =parent * 2 +1;
	while (child<size)
	{
		if ((child+1<size)&&a[child + 1] <a[child])//若右孩子存在且小于左孩子
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			//交换
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}else
		{
			break;
		}
	}

}
//向下调整建堆
void heapsort4(int* a, int n)
{
	HP f;
	Heapinit(&f);
	//向下调整建小堆
	//与向生调整建堆相反,这里是从数组后面开始调整堆,也就是从二叉树的下面开始
	for (int i =(n-1-1)/2 ; i >=0; i--)
	{
		Adjustdown1(a, n, i);
	}
	int end = n-1;
	while (end>0)
	{
		//进行排序
		int tmp = a[0];
		a[0] = a[end];
		a[end] = tmp;
		Adjustdown1(a, end, 0);
		--end;
	}

}

建大堆---排序结果为升序

void Adjustdown2(HPDATAtype* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if ((child + 1 < size) && a[child + 1] > a[child])//若右孩子存在且小于左孩子
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			//交换
			int tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}
void heapsort5(int* a, int n)
{
	HP f;
	Heapinit(&f);
	//向下调整建大堆
	//与向生调整建堆相反,这里是从数组后面开始调整堆,也就是从二叉树的下面开始
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown2(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//进行排序
		int tmp = a[0];
		a[0] = a[end];
		a[end] = tmp;
		Adjustdown2(a, end, 0);
		--end;
	}

}

向上与向下比较

根据计算我们发现向下调整建堆是优于向上调整建堆的,这里的对于向下调整算法实现复杂度是O(N),向上调整算法的时间复杂度为(N*logN),应为向下调整算法,就如同在数组中插入,而向上调整算法经过错位相减或等比数列法计算大概为N*logN)。文章来源地址https://www.toymoban.com/news/detail-483089.html

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

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

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

相关文章

  • 数据结构——堆的应用

    堆结构主要有两个应用:1、堆排序 2、topK问题 现实中,排序是非常常见的,比如排序班级同学的各科分数,购物时,商品会按销量,价格,好评数等进行排序。相信大家也不喜欢再购物筛选时,加载半天出不来吧!一个好的排序用的时间会大大减少,改善用户的体验。堆排

    2024年04月10日
    浏览(77)
  • 【数据结构】堆的实现及应用

    简单不先于复杂,而是在复杂之后 。 1.1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系

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

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

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

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

    2024年03月14日
    浏览(59)
  • 数据结构——堆的应用 堆排序详解

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

    2024年03月11日
    浏览(50)
  • 【数据结构】堆的应用——Top-K

    目录 前言: 一、Top-K问题描述: 二、不同解决思路实现: ①.排序法: ②.直接建堆法: ③.K堆法 总结:         上篇文章我们学习了二叉树的顺序存储结构,并且对于实际使用中所常用的顺序存储结构——堆的各个接口进行实现。这篇文章我们将对堆的实际应用进行更加

    2024年02月16日
    浏览(53)
  • 数据结构第十二弹---堆的应用

    要学习堆排序,首先要学习堆的向下调整算法,因为要用堆排序,你首先得建堆,而建堆需要执行多次堆的向下调整算法。 但是,使用向下调整算法需要满足一个前提:  若想将其调整为小堆,那么根结点的左右子树必须都为小堆。  若想将其调整为大堆,那么根结点的左

    2024年02月02日
    浏览(38)
  • 数据结构 - 堆(优先队列)+ 堆的应用 + 堆练习

    1、本文章适合新学和复习用,都是用c语言实现的,包含了堆的讲解、堆的应用、堆的练习。 2、有图解和代码都注释,放心食用哦 那么开始: 一、什么是堆 堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组

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

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

    2024年02月13日
    浏览(41)
  • 【数据结构和算法】---二叉树(2)--堆的实现和应用

    如果有一个数字集合,并把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ,且在逻辑结构(即二叉树)中,如果 每个父亲节点都大于它的孩子节点那么此堆可以称为大堆 ;那么如果 每个父亲节点都小于它的孩子节点那么此堆可以称为小堆 。 堆的 性质

    2024年02月03日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包