堆的基本操作（c语言实现）

堆的基本操作（c语言实现）

码农世界 2024-06-08 后端 89 次浏览 0个评论

 1.堆的基本操作

1.1定义堆

typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{
	HPDataType* a;//用于存储数据的数组
	int size;//记录堆中已有元素个数
	int capacity;//记录堆的容量
}HP;

1.2初始化堆

然后我们需要一个初始化函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。

//初始化堆
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);
	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);//申请一个堆结构
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	php->a = tmp;
	memcpy(php->a, a, sizeof(HPDataType)*n);//拷贝数据到堆中
	php->size = n;
	php->capacity = n;
	int i = 0;
	//建堆
	for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

1.3 销毁堆

 为了避免内存泄漏，使用完动态开辟的内存空间后都要及时释放该空间，所以，一个用于释放内存空间的函数是必不可少的。

//销毁堆
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);//释放动态开辟的数组
	php->a = NULL;//及时置空
	php->size = 0;//元素个数置0
	php->capacity = 0;//容量置0
}

1.4打印堆

 打印堆中的数据，这里用的打印格式是按照堆的物理结构进行打印，即打印为一排连续的数字。

//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	//按照物理结构进行打印
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

1.5堆的插入

 数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。

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

 这个插入的效果完全取决于AdjustUp函数是给大堆设计的还是小堆！！

1.6堆的删除

堆的删除操作通常指的是从堆中移除最大值或最小值的操作。

在最大堆中，根节点是最大的元素，而在最小堆中，根节点是最小的元素。

以下是堆的删除操作的基本思路：

  1. 首先，将堆顶元素（即根节点）与最后一个元素交换位置，即将最大值或最小值移动到数组的末尾。
  2.  然后，将堆的大小减1，即删除了原来堆顶的元素。
  3. 最后，对新的堆顶元素进行向下调整，以保持堆的性质。在最大堆中，需要将新堆顶元素与其子节点中的较大者交换，直到满足最大堆的性质；在最小堆中，需要将新堆顶元素与其子节点中的较小者交换，直到满足最小堆的性质。

通过以上步骤，可以实现堆的删除操作，并保持堆的性质不变。

//堆的删除
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);//向下调整
}

这段代码是堆的删除操作，基本思路如下：

1. 首先，通过断言（assert）确保传入的堆指针（php）不为空，并且堆不为空。

2. 然后，将堆顶元素（索引为0的元素）与最后一个元素进行交换，即将堆顶元素移动到数组的末尾。

3. 接着，将堆的大小减1，即删除了原来堆顶的元素。

4. 最后，调用AdjustDown函数对新的堆顶元素进行向下调整，以保持堆的性质。

1.7.获取堆的数据个数

获取堆的数据个数，即返回堆结构体中的size变量。

//获取堆中数据个数
int HeapSize(HP* php)
{
	assert(php);
	return php->size;//返回堆中数据个数
}

1.8堆的判空

堆的判空，即判断堆结构体中的size变量是否为0。

//堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;//判断堆中数据是否为0
}

2.完整操作加测试代码

#include
#include
#include
#include
#include
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType x = *p1;
	*p1 = *p2;
	*p2 = x;
}
//堆的向下调整（小堆）—— 左右子树都是小堆
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;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//初始化堆
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);
	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * n);//申请一个堆结构
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	php->a = tmp;
	memcpy(php->a, a, sizeof(HPDataType) * n);//拷贝数据到堆中
	php->size = n;
	php->capacity = n;
	int i = 0;
	//建堆
	for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

//堆的向上调整（小堆）
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 = (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);
}
//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	//按照物理结构进行打印
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
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);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
int main()
{
	HP hp;
	int a[] = { 4,18,42,12,21,3,5,5,88,5,5,15,5,45,5 };
	int size = sizeof(a) / sizeof(a[0]);
	HeapInit(&hp,a,size);
	HeapPrint(&hp);
	HeapPop(&hp);
	HeapPrint(&hp);
	HeapPush(&hp, 4);
	HeapPrint(&hp);
	return 0;
}

堆的基本操作（c语言实现）

我们可以来验证一下是不是堆

堆的基本操作（c语言实现）

  1. 堆的向上调整和向下调整的代码一定要是匹配的，小堆的只能和小堆匹配使用，大堆的只能和大堆匹配使用，要不然就会让你十分抓马 ，我就是因为错误匹配使用就导致了痛苦了两个晚上……
  2. 还有就是大家一定要去画图去验证一下这个是不是堆，不要用眼睛看
  3. 其次就是一定要建好堆后再使用堆的向上调整和向下调整

转载请注明来自码农世界，本文标题：《堆的基本操作（c语言实现）》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，89人围观）参与讨论

还没有评论，来说两句吧...

Top