什么是堆,如何实现?(附堆排序,TOP-K问题)

这篇具有很好参考价值的文章主要介绍了什么是堆,如何实现?(附堆排序,TOP-K问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

欢迎来到 Claffic 的博客 💞💞💞

什么是堆,如何实现?(附堆排序,TOP-K问题)

“春风里,是谁 花一样烂漫?”

前言:

二叉树给大家讲解的差不多了,接下来就是二叉树的实际应用了:这期我们来讲堆,它是一种顺序结构的特殊二叉树,可以实现排序等功能,那就让我们开始吧!


目录

🌸Part1: 何为堆

1.堆的概念

2.堆的结构

🌺Part2: 堆的实现 

1.前期准备

1.1项目创建

1.2结构定义

1.3堆的初始化

2.相关功能实现

2.1堆插入数据

2.2堆删除数据 

2.3数组建堆

2.4判断堆是否为空

2.5获取堆顶元素

2.6堆的销毁

🌹Part3: 堆的应用

3.1堆排序(排升序)

3.2 TOP-K问题


Part1: 何为堆

1.堆的概念

将元素按照完全二叉树的顺序存储方式存储在一个一维数组中,并满足对应根结点数值大于两个孩子结点(称为大堆)或者小于两个孩子结点(称为小堆)。

单看概念是不足以理解的,与结构结合理解会更好:

2.堆的结构

还记得上期的 逻辑结构 物理结构 吗?

什么是堆,如何实现?(附堆排序,TOP-K问题)

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

堆的本质呢,是 数组 ,不过对数组中存储的数据顺序有着特殊的要求: 

大堆:根节点数值大于两个孩子结点的数值;

小堆:根节点数值小于两个孩子结点的数值。

上例子: 

什么是堆,如何实现?(附堆排序,TOP-K问题)

这是一个大堆

什么是堆,如何实现?(附堆排序,TOP-K问题)

这是一个小堆

到这里,相信你已经知道什么是堆了。

记住堆的性质:

• 堆总是一颗完全二叉树

• 堆中某个结点的数值总是不大于不小于双亲结点

Part2: 堆的实现 

1.前期准备

1.1项目创建

Heap.h:头文件,声明所有函数;

Heap.c:源文件,实现各函数;

Test.c:  源文件,主函数所在项,可调用各函数。

1.2结构定义

堆的本质就是一个数组嘛,

默认整型数组,为方便相关操作的实现,再定义大小size和容量capacity

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

1.3堆的初始化

这里选择动态开辟内存,

初始容量为4个整型大小: 

//堆的初始化
void HeapInit(HP* php)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	php->capacity = 4;
	php->size = 0;
}

2.相关功能实现

注意:我们这里默认实现大堆 

2.1堆插入数据

插入数据前,要先判断下有没有满,定义容量和大小的好处就在这里,

直接通过 容量和大小是否相等 就可以,

如果满,默认扩展至先前容量的两倍;

if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;

接下来就是对插入的数据进行调整了,

要注意:插入之前就是大堆或小堆(默认大堆)

我们需要做的就是将插在末尾的数据通过比较交换,使其在最合适的位置

这里用到的是 向上调整

什么是堆,如何实现?(附堆排序,TOP-K问题)

第一次做这种动图🤣🤣🤣

如图所示,在数组末尾插入数据后,需要跟双亲结点比较,再决定是否向上调整。

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

 所以最终代码:

//堆插入数据 向上调整 插入之前就是堆
void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * php->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

2.2堆删除数据 

大堆删除数据,是指删除 最大根节点

那么怎样才能保证删除第一个数据之后,剩余的结点的双亲结点与孩子结点关系不乱呢? 

这里有一个巧妙的办法: 

先将第一个结点与最后一个结点 交换 ,再 删除 最后一个结点,最后 向下调整

什么是堆,如何实现?(附堆排序,TOP-K问题)

最后仍然保持是一个大堆

代码实现:

//堆删除数据  向下调整
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);

}
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
        //先判断child,防止越界,挑出较大的孩子结点
		if (child < n + 1 && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.3数组建堆

任意给一个数组,可不能保证它就是堆,

所以要利用数组来建堆,也叫用数组初始化堆。

前半部分的空间开辟不必多讲,重点放在建堆(默认建大堆)上:

方法一:向上调整

给一个数组,先从第一个数开始,逐渐扩大区间,每扩大一次就进行一次向上调整;

其实就是 模拟插入数值 罢了。


//建堆(默认建大堆),向上调整
for (int i = 1; i < n; i++)
{
	AdjustUp(a, i);
}

方法二:向下调整

这种方法是从倒数第二层数组开始调整,依次向下调整。


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

两种方法对比: 

这里先告诉大家结论:

向下调整建堆(时间复杂度为:O(N))要优于向上调整建堆(时间复杂度为:O(N*logN)

准确计算方式:其实就是每层的结点个数乘以要向下/向上调整的层数,最后求和,比较下即可。

简单理解:

向下调整:结点多的调整次数少,结点少的调整次数多;

向上调整:结点少的调整次数少,结点多的调整次数多;

就这个描述,向下调整更平衡一些,在这种粗略理解下,向下调整优于向上调整。

2.4判断堆是否为空

直接判断大小是否为0即可。

//判空
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

2.5获取堆顶元素

返回数组的第一个值即可。

//获取堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);

	return php->a[0];
}

2.6堆的销毁

将数组释放置空,容量和大小归零。 

//堆的销毁
void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

Part3: 堆的应用

3.1堆排序(排升序)

给你一个数组,要进行堆排序,首先要把它 变成堆

考虑下这个问题:排升序,建大堆还是小堆?

答案是 建大堆

因为大堆的最大根节点就是整个堆中最大的,我们只需要将这个最大值调整到最后就可以了;

如果是小堆,我们不能保证两个孩子结点的大小关系,调整起来就比大堆麻烦。

再者就是优先选择 向下调整 ,效率较高。

//向下调整(效率更高)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a, n, i);
}

建完大堆,接下来就是数据位置的调整了: 

将最大根节点调整到最后,然后通过调整,保持剩余结点依然是一个大堆。

是不是感觉与删除操作有些相似?

是的,这可以理解为 模拟删除操作 ,只不过被删除的数还是要保留的。

最终代码:

//堆排序
void HeapSort(int* a, int n)
{
	//向下调整(效率更高)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end--)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
	}
}

3.2 TOP-K问题

给一个情景:

在世界所有的企业中选出世界500强。

这就涉及到TOP-K问题,简单理解,TOP-K问题就是在N个数字中选出K个数字,保证这K个数字任何一个都比剩余N-K个数字大。

建堆是必须的,但建大堆还是小堆?

这里有一个巧妙的办法:

1.前K个数字先建成一个小堆

2.遍历剩余N-K个数字,遇到比堆顶数字大的就替它进堆,再进行向下调整。

这种方法巧妙在 大数向下沉,小数向上浮。最后大数把小数挤出堆,堆里的都是大数。

为了创建大量数据,这里利用随机数,将数据存储在文件当中:

void PrintTopK(const char* file, int k)
{
	// 用a中前k个元素建小堆
	int* topk = (int*)malloc(sizeof(int) * k);
	assert(topk);

	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

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

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

	// 将剩余n-k个元素依次与堆顶元素交换,不满就替换
	int val = 0;
	int ret = fscanf(fout, "%d", &val);
	while (ret != EOF)
	{
		if (val > topk[0])
		{
			topk[0] = val;
			AdjustDown(topk, k, 0);
		}

		ret = fscanf(fout, "%d", &val);
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", topk[i]);
	}
	printf("\n");

	free(topk);
	fclose(fout);
}

 

代码已上传至 我的gitee

拿走不谢~ 


总结:

这期知识密度较大,不仅有堆的实现,还有两个堆的应用,建议先将堆实现一波,再进行两个应用问题的解决~~~

码文不易 

如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦  💗💗💗文章来源地址https://www.toymoban.com/news/detail-409957.html

到了这里,关于什么是堆,如何实现?(附堆排序,TOP-K问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 堆的实现,画图和代码分析建堆,堆排序,时间复杂度以及TOP-K问题

    如果有一个关键码的集合K = {k 0 ,k 1 ,k 2 ,…,k n-1 },把它的所有元素按 完全二叉树 的顺序存储方式存储在一个一维数组中,并满足:k i =k 2*i+1 且 =k 2*i+2 (k i =k 2*i+1 且 =k 2*i+2 ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫

    2024年02月04日
    浏览(40)
  • 堆排序之“TOP-K”问题

    目录 一、什么是TOP-K问题 二、解决思路  一般的正常思路: 最优的解决思路: 三、文件流中实践TOP-K方法  创建包含足够多整数的文件: 向下调整算法 找出最大的K个数 完整版代码: 前面我已经学习过使用“堆排序”对数组排降序了,接下来再来看一个堆排序的应用场景。

    2024年02月06日
    浏览(41)
  • 数据结构与算法:堆排序和TOP-K问题

    朋友们大家好,本节内容来到堆的应用:堆排序和topk问题 我们在c语言中已经见到过几种排序,冒泡排序,快速排序(qsort) 冒泡排序的时间复杂度为O(N 2 ),空间复杂度为O(1);qsort排序的时间复杂度为 O(nlogn),空间复杂度为O(logn),而今天所讲到的堆排序在时间与空间复杂度上相

    2024年03月08日
    浏览(62)
  • 堆(两种建堆方法)、堆排序和Top-K问题

    是一种完全二叉树,分为大堆,小堆 如果有一个关键码的集合 int K[ ] = {27,15,19,18,28,34,65,49,25,37} ; 把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:K i =K 2*i+1 且K i =K 2*i+2 ( K i =K 2*i+1 且K i =K 2*i+2 ) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大

    2023年04月09日
    浏览(34)
  • 【数据结构】---堆排序+TOP-K问题(了解游戏排行底层原理)

    👧个人主页:@小沈熬夜秃头中୧⍤⃝❅ 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:数据结构 🔑本章内容:堆排序+TOP-K问题 送给各位💌:日落跌入昭昭星野 人间忽晚 山河以秋 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面

    2024年02月06日
    浏览(47)
  • 数据结构之堆排序以及Top-k问题详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力 目录 1.前言 2.堆排序 2.1降序排序 2.2时间复杂度 3.Top-k问题 4.总结         在上一篇文

    2024年02月05日
    浏览(43)
  • 【数据结构】二叉树-堆(top-k问题,堆排序,时间复杂度)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​ 目录 堆排序 第一种  ​编辑 第二种  TOP-K问题 建堆的时间复杂度 向下调整建堆的时间复杂度:  向上调整建堆的时间

    2024年01月21日
    浏览(61)
  • 数据结构进阶篇 之 【堆的应用】(堆排序,TOP-K问题)详细讲解

    所有人都关心我飞的高不高,只有我妈关心我翅膀硬不硬 1.1 建堆 1.2 利用堆删除思想来进行排序 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 学习一个知识,我们起码要直

    2024年04月10日
    浏览(47)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(45)
  • 数据结构--堆的实现-大根堆/小根堆/堆排序/堆排序稳定性证明/TOP-K

            前言          逆水行舟,不进则退!!!                目录        认识堆        堆的创建         1,向下调整的方法建立堆         2,以向下调整的方式建立小根堆         3,向上调整的方式建堆        堆的插入        堆的删除              

    2024年02月04日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包