数据结构——堆(C语言实现)

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

什么是堆

堆是一种特殊的数据结构,它是一棵完全二叉树,同时满足堆属性,即父节点的值总是大于或小于其子节点的值。如果父节点的值总是大于子节点的值,那么我们称之为大根堆;反之,如果父节点的值总是小于子节点的值,那么我们称之为小根堆。在堆中,根节点的值最大(大根堆)或最小(小根堆),因此它也被称为堆顶。堆经常用于排序、topK问题等场景。
数据结构——堆(C语言实现)

堆的实现

本篇文章使用c语言实现并以头文件和源文件分离的形式,也会逐步介绍各个接口的实现思路以及提供参考代码。

堆的结构定义

堆的结构定义其实是一个特殊的顺序表,这点和栈类似。所以,需要用一个指针指向动态开辟的内存,需要一个指向当前下标位置的变量,以及需要一个记录当前动态内存的容量。
数据结构——堆(C语言实现)

堆的初始化接口

堆初始化接口实现思路如下,首先,改变一个堆,我们需要传它的地址。所以参数部分需要写成Hp*。在接口的一开始先判断指针的合法性。然后开辟动态内存,判断一下动态内存的有效性。最后,初始化结构体成员即可。
数据结构——堆(C语言实现)

堆的销毁接口

释放动态申请的空间,free后及时置空的好习惯是我们应该要养成的。最后将size和capacity置零即可。
数据结构——堆(C语言实现)

堆的插入数据接口

堆的插入接口实现思路如下,assert判断指针有效性,这是一个好的编程习惯,建议大家平时也养成这种习惯。首先判断容量是否满了,满了的话就扩容。然后直接下面的插入数据逻辑,其实就是类似于顺序表。直接将数据插入size下标的位置,++size即可。最后调用向上调整建堆接口,使堆的结构不变。
数据结构——堆(C语言实现)

向上调整建堆接口

首先要根据孩子的下标位置,推断出父节点的下标位置。然后开始向上调整,向上调整的过程是一个循环的过程,循环的迭代条件就是当child大于根节点下标就继续支持循环。当子节点小于父节点循环终止。若父节点小于子节点那么进行对应下标的数据交换,然后迭代子节点下标和父节点下标即可。
数据结构——堆(C语言实现)

数据结构——堆(C语言实现)

判断堆是否为空

判断堆是否为空接口思路相对简单,类似于顺序表的判空思路,当下一个可以插入数据的下标为0时,表示为空堆。
数据结构——堆(C语言实现)

堆的删除数据接口

要删除堆的数据,是删除堆的堆顶数据还是堆底数据呢?答案是删除堆顶的数据,因为删除堆底的数据没有什么价值。而删除堆顶可以产生一些价值,如排序或者对一些前排名K个的数据进行收集等。举个例子,当我们在购物app想选一个电脑,我们可以按照销量进行排序这也是堆应用的一个场景。回到正题,删除堆顶的实现思路如下,我们让堆顶数据和最后一个数据交换,然后让size–,达到删除堆顶数据的效果,并且大大提升了效率。最后向下调整建堆即可。
数据结构——堆(C语言实现)

数据结构——堆(C语言实现)

向下调整建堆接口

向下调整建堆实现思路如下,首先,向下调整的过程是一个循环,它的终止条件为parent > size。循环体内部就是向下调整的核心思路,parent跟左右孩子较大的(较小的)比,本文以实现大堆为例。这里要介绍一个比较重要的概念,由于堆的底层使用顺序表存储,所以同一个父亲的左孩子右孩子是相邻存储的。即左孩子下标+1就是右孩子下标。让父亲和左右孩子较大的那一个比较,如果父亲小于孩子就交换位置,然后迭代。注意:向下调整的条件是左右子树必须是堆。
数据结构——堆(C语言实现)

获取堆顶数据

其实,就是访问顺序表的第一个元素。但是,这样提供一个接口是非常符合接口的一致性以及对于代码的可读性有极大的提升的。
数据结构——堆(C语言实现)

获取堆的有效数据个数

由于我们的size是从0开始,所以直接return size即可。
数据结构——堆(C语言实现)

完整实现代码

//Heap.h文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//默认起始容量
#define DefaultCapacity 4

//存储的数据类型
typedef int HpDataType;

typedef struct Heap
{
	HpDataType* data;
	int size;//可以插入数据的下标
	int capacity;//容量
}Hp;


//初始化
void HpInit(Hp* pHp);

//堆的销毁
void HpDestroy(Hp* pHp);

//插入数据
void HpPush(Hp* pHp, HpDataType x);

//向上调整建堆
void AdjustUp(HpDataType* data, int child);

//判断是否为空
bool HpEmpty(Hp* pHp);

//删除数据
void HpPop(Hp* pHp);

//向下调整建堆
void AdjustDown(HpDataType* data,int size, int parent);

// 取堆顶的数据
HpDataType HpTop(Hp* pHp);

// 堆的数据个数
int HpSize(Hp* pHp);
// Heap.c文件
#include"Heap.h"

//初始化
void HpInit(Hp* pHp) 
{
	//判断合法性
	assert(pHp);

	//开辟动态空间
	HpDataType* tmp = (HpDataType*)malloc(sizeof(HpDataType) * DefaultCapacity);
	if (tmp == NULL)//判断合法性
	{
		perror("malloc fail");
		return;
	}

	//初始化
	pHp->data = tmp;
	pHp->size = 0;
	pHp->capacity = DefaultCapacity;
}

//堆的销毁
void HpDestroy(Hp* pHp)
{
	//判断合法性
	assert(pHp);

	//释放内存和清理
	free(pHp->data);
	pHp->data = NULL;
	pHp->size = pHp->capacity = 0;

}


void Swap(HpDataType* p1, HpDataType* p2)
{
	HpDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整建堆
void AdjustUp(HpDataType* data, int child)
{
	//判断指针有效性
	assert(data);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//向上调整呢
		if (data[child] > data[parent])
		{
			Swap(&data[child], &data[parent]);
		}
		else
		{
			break;
		}	
		//迭代
		child = parent;
		parent = (child - 1) / 2;
	}

}

//插入数据
void HpPush(Hp* pHp, HpDataType x)
{
	//判断指针有效性
	assert(pHp);

	//判断容量是否满了
	if (pHp->size == pHp->capacity)
	{
		HpDataType* tmp = (HpDataType*)realloc(pHp->data,sizeof(HpDataType) * pHp->capacity * 2);
		if (tmp == NULL)//判断空间合法性
		{
			perror("malloc fail");
			return;
		}
		//扩容后
		pHp->data = tmp;
		pHp->capacity *= 2;
	}

	//数据入堆
	pHp->data[pHp->size] = x;
	pHp->size++;

	//向上调整建堆
	AdjustUp(pHp->data, pHp->size - 1);

}
void AdjustDown(HpDataType* data, int size, int parent)
{
	//断言检查
	assert(data);

	int child = parent * 2 + 1;

	while (child < size)
	{
		//求出左右孩子较大的那个下标
		if (child + 1 < size && data[child + 1] > data[child])
		{
			child++;
		}
		//父亲比孩子小就交换位置
		if (data[child] > data[parent])
		{
			//交换
			Swap(&data[child], &data[parent]);
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

void HpPop(Hp* pHp)
{
	//断言检查
	assert(pHp);

	//删除数据
	Swap(&pHp->data[0], &pHp->data[pHp->size-1]);
	pHp->size--;

	//向下调整建堆
	AdjustDown(pHp->data,pHp->size-1,0);

}

//判断是否为空
bool HpEmpty(Hp* pHp)
{
	assert(pHp);
	
	return pHp->size == 0;
}

// 取堆顶的数据
HpDataType HpTop(Hp* pHp)
{
	assert(pHp);

	return pHp->data[0];
}

// 堆的数据个数
int HpSize(Hp* pHp)
{
	assert(pHp);

	return pHp->size;
}

小结

操作堆这种数据结构就像吃老婆饼,你吃的是香甜的饼,至于是不是你老婆做的那就不一定了。但是,你在吃的时候想像成你老婆做的饼吃起来也别有一番风味。堆在逻辑结构上你操作的是一颗树,在底层的存储上又是一个顺序表。这就比较抽象的地方,需要考验我们画图以及走读代码调试的能力。

堆排序

堆排序其实就是堆这个数据结构的一种常见的使用方式。堆排序的核心思想就是利用堆删除的思想来进行排序操作。堆排序是一种时间复杂度O(N*logN)的不稳定排序。至于排序的稳定性的讲解在后面的博客会给大家介绍。

堆排序的实现

堆排序的实现思路如下,首先确定排序的顺序并将数据建成堆,升序建大堆,降序建小堆。建堆的话建议使用向下调整建堆。因为时间复杂度为O(logN),若使用向上调整建堆,那么时间复杂度为O(N*logN)。这样的时间复杂度对于找出堆顶数据的损耗太大,还不如直接遍历一遍(时间复杂度)。
数据结构——堆(C语言实现)

接着是利用堆删除的思想进行排序。下面就以排升序为例。
数据结构——堆(C语言实现)

//堆排序--排升序建大堆
void HeapSort(int* arr, int n)
{
	//向下建堆,效率更高
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr,n-1,i);
	}

	//排序
	//利用堆删除的思想进行排序
	int end = n - 1;
	while (end > 0)
	{
		//交换
		int tmp = arr[0];
		arr[0] = arr[end];
		arr[end] = tmp;
		//调整堆
		AdjustDown(arr, end-1, 0);
		end--;
	}
}

关于建堆和堆排序时间复杂度的分析

向下调整建堆

在前面的堆排序实现中,提到向下调整建堆的效率更高,这是因为向下调整建堆的时间复杂度是O(N)。下面我就带领大家简单分析一下向下调整建堆的时间复杂度。
数据结构——堆(C语言实现)

向上调整建堆

向上调整建堆的时间复杂度为O(N*logN)。下面请看向上调整的时间复杂度问题。
数据结构——堆(C语言实现)

堆排序

堆排序的时间复杂度为O(NlogN)。向下调整建堆的复杂度为O(N),要排序的个数为N-1趟,可以算作O(N),交换完后的向下调整建堆的时间复杂度为O(LogN),所以对排序的时间复杂度为O(2NLogN)。
数据结构——堆(C语言实现)

小结

上面介绍的建堆时间复杂度和堆排序复杂度,记个结论其实就可以了。当然,从实现的角度上也不难分析出向上调整建堆和向下调整建堆的大致效率上的差距。因为向下调整从第一个非叶子结点开始调整,最坏的情况下也要比向上调整少调整一半的结点。这在效率上已经胜出不少了。

TOPK问题的介绍

TOPK问题是指在一组数据中,找出前K个最大或最小的数据的问题,常见的解决方法包括堆排序、快速排序、归并排序等。该问题在数据分析、机器学习等领域中经常出现。当然有一种特殊场景下用堆进行TOK的筛选非常的妙。假设现在有100亿个整数,要求出前50个数,我们可以建一个小堆,只要遍历的数据比堆顶数据大就替代它进堆(向下调整),最终就可以得到最大的前五十个数。下面用一个样例简单感受一下。文章来源地址https://www.toymoban.com/news/detail-479703.html

void AdjustDownSH(HpDataType* data, int size, int parent)
{
	//断言检查
	assert(data);

	int child = parent * 2 + 1;

	while (child < size)
	{
		//求出左右孩子较大的那个下标
		if (child + 1 < size && data[child + 1] < data[child])
		{
			child++;
		}
		//父亲比孩子小就交换位置
		if (data[child] < data[parent])
		{
			//交换
			Swap(&data[child], &data[parent]);
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

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

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

	// 读出前k个数据建小堆
	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", &topk[i]);
	}

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

	// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
	int val = 0;
	int ret = fscanf(fout, "%d", &val);
	while (ret != EOF)
	{
		if (val > topk[0])
		{
			topk[0] = val;
			AdjustDownSH(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);
}

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

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

	fclose(fin);
}

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

	return 0;
}

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

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

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

相关文章

  • 【数据结构】特殊矩阵的压缩存储

    🌈 自在飞花轻似梦,无边丝雨细如愁 🌈   🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录 🌟 数组是由n个相同类型的数据元素所构成的有限序列 数组和线性表的关系: 数组是线性表的推广:一维数组可以看做是一个线性表,而对于二维数组而言,可以看成是有

    2024年02月11日
    浏览(48)
  • 数据结构--特殊矩阵的压缩存储

    各数组元素大小相同,且物理上连续存放。 数组元素a[i]的存放地址= LOC + i * sizeof(ElemType) ( 0 ≤ i 10 ) (0le i 10) ( 0 ≤ i 10 ) 注:除非题目特别说明,否则数组 下标默认从 0 开始 color{red}下标默认从0开始 下标默认从 0 开始 注意审题 ! 易错 ! color{purple}注意审题!易错! 注意审题

    2024年02月16日
    浏览(61)
  • 数据结构— 数组、特殊矩阵、稀疏矩阵

    💟作者简介:大家好呀!我是 路遥叶子 ,大家可以叫我 叶子 哦! ❣️     📝个人主页:【路遥叶子的博客】 🏆博主信息: 四季轮换叶 , 一路招摇胜!      专栏 【数据结构-Java语言描述】  【安利Java零基础】 🐋希望大家多多支持😘一起进步呀!~❤️ 🌈若有帮助

    2024年02月02日
    浏览(53)
  • 【数据结构】特殊的线性表——栈

    🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧上一篇文章:从链表到LinkedList类🎈🎈🎈🎈🎈 什么叫栈?要搞清楚这个概念,首先要明白“栈”原来的意思,如此才能把握本质。栈,存储货物或供旅客住宿的地方,可引申

    2024年03月15日
    浏览(65)
  • 探索数据结构:特殊的双向队列

    ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:数据结构与算法 贝蒂的主页:Betty’s blog **双向队列(double‑ended queue)**是一种特殊的队列,它允许在队列的队尾与队头插入与删除元素。根据其定义,我们也可以理解为两个栈在栈底相连。

    2024年04月09日
    浏览(43)
  • 数据结构(五)----特殊矩阵的压缩存储

    目录 1.一维数组的存储结构 2.二维数组的存储结构 3.普通矩阵的存储 4.特殊矩阵的压缩存储 (1)对称矩阵 (2)三角矩阵 (3)三对角矩阵 (4)稀疏矩阵的压缩存储 1.一维数组的存储结构 一维数组的定义如下: ElemType a[10]; 各数组元素大小相同,且物理上连续存放。 数组元

    2024年04月28日
    浏览(39)
  • 24考研数据结构-数组和特殊矩阵

    数据结构是计算机科学中的基础概念,它涉及组织和存储数据的方式以及对数据的操作。在数据结构中,数组和特殊矩阵是两种常见的数据组织形式。本文将对数组和特殊矩阵进行介绍,并讨论它们在实际应用中的特点和用途。 数组是一种线性数据结构,它由相同类型的元素

    2024年02月14日
    浏览(37)
  • 【算法 & 高级数据结构】树状数组:一种高效的数据结构(二)

    🚀 个人主页 :为梦而生~ 关注我一起学习吧! 💡 专栏 :算法题、 基础算法、数据结构~赶紧来学算法吧 💡 往期推荐 : 【算法基础 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理) 【算法基础】深搜 数据结构各内部排序算法总结对比及动图演示(插入排序

    2024年03月26日
    浏览(85)
  • 【算法 & 高级数据结构】树状数组:一种高效的数据结构(一)

    🚀 个人主页 :为梦而生~ 关注我一起学习吧! 💡 专栏 :算法题、 基础算法~赶紧来学算法吧 💡 往期推荐 : 【算法基础 数学】快速幂求逆元(逆元、扩展欧几里得定理、小费马定理) 【算法基础】深搜 树状数组 (Binary Indexed Tree,BIT)是一种数据结构,用于高效地处理

    2024年03月11日
    浏览(68)
  • 【考研】数据结构——特殊矩阵的压缩存储(含真题)

    本文内容源于对《数据结构(C语言版)》(第2版)、王道讲解学习所得心得、笔记整理和总结。 本文主要以举例子的方式讲解考研选择题型中的特殊矩阵的压缩存储知识点,配以图文(含408真题)。 可搭配以下链接进行学习: 【2023考研】数据结构常考应用典型例题(含真

    2024年02月03日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包