数据结构之【堆的实现】

2023-12-29 21:12:28

通过前几次的博客我们大致了解了堆的性质，接下来我们用数据结构来封装堆

注意本篇博客建堆建的是大堆。

首先建堆

typedef int HPDataType;
struct Heap
{
	HPDataType* a; //数组
	int size;      //大小
	int capacity;  //容量
};

typedef struct Heap HP;

 实现以下几种接口：

void HeapInit(HP* php, HPDataType* a, int n);  //初始化
void HeapDestory(HP* php);   //销毁
void HeapPush(HP* php, HPDataType x);  //入一个数据，仍然是堆
void HeapPop(HP* php);   // 删除
HPDataType HeapTop(HP* php);  // 返回堆顶
int HeapSize(HP* php); // 统计大小
bool HEapEmpty(HP* php);  //判断堆是否为空
void HeapPrint(HP* php);  // 打印

 初始化的实现

void HeapInit(HP* php, HPDataType* a, int n);  //初始化

形参中的HP* php,相当于是把结构体的地址给这个函数了，可以直接使用这个结构体

第一步：我们首先要给php 里面的数组开空间（也就是php->a）。

第二步我们要把我们自己创建的数组（HPDataType* a）的内容拷贝到php里面的数组中（也就是php->a）。

第三步进行建堆。

我们不直接对数组进行处理的原因是我们要把php->a 做成堆，并且待会还要支持插入，删除等操作，就必须是要自己malloc的，因为如果待会数组空间不够需要自己增容

拷贝有两种方式

第一种用个for循环

for (int i = 0;i < n;i++)
	{
		php->a[i] = a[i];
	}

	php->size = n;
	php->capacity = n;

第二种直接用，memcpy函数

memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;

 接下来，建堆

for (int i = (php->size - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(php->a , php->size, i);
	}

完整代码：

void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	for (int i = (php->size - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(php->a , php->size, i);
	}  

}

 这里的AdjustDown（向下调整算法）之前已经实现过，现在不再赘述。

销毁的实现

释放掉php->a的空间，将大小size与容量置为0即可

void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}

 入数据的实现

首先检查下空间（php->a）是否足够不够就进行扩容，接着插入数据。

 因为堆的本质就是数组，插入一个数据，就是在数组最后加一个空间，增加一个数据

但是插入完数据后，还得要保证这个数组仍然是一个堆

如下图：

数据结构之【堆的实现】

 对于第二种插入88 的情况，我们就需要将88 进行向上调整

思路就是，如果孩子比父母大就交换，交换之后，父母就成为新的孩子，依次循环，直到孩子到达初始位置，如果孩子比父母小，直接终止循环即可。

代码如下：

void Adjustup(int* 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;
		}
	}
}

ps:如果建的是小堆，只需要吧大于改成小于即可 

完整代码如下：

void HeapPush(HP* php, HPDataType x)
{
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;
	Adjustup(php->a, php->size - 1);
 
}

 删除的实现

删除堆的一个数据，指的是删除堆顶的数据，

如果我们采用后面覆盖前面的方式删除，那么时间复杂度就是O(N),并且堆的结构都打乱了，还需要重新建堆又是O(N)，效率太低了

所以我们采用之前堆排序的思想，交换堆顶与堆底的数据，删除新的堆底的数据，然后进行一次向下调整，时间复杂度是O(logN)

代码如下：

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

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

}

 返回堆顶实现

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

 统计堆中数据个数

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

 检测堆是否为空

bool HEapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

打印接口的实现

void HeapPrint(HP* php)
{
	for (int i = 0;i < php->size;i++)
	{
		printf("%d ", php->a[i]);

	}
	printf("\n");

	int num = 0;
	int level = 1;
	for (int i = 0;i < php->size;i++)
	{
		printf("%d ", php->a[i]);
		num++;
		if (num == level)
		{
			printf("\n");
			level *= 2;
			num = 0;
		}
	}
	printf("\n");
	printf("\n");
}

 完整代码及演示

Heap.h 部分

#include<stdlib.h>
#include<assert.h>
#include<string.h>



typedef int HPDataType;
struct Heap
{
	HPDataType* a; //数组
	int size;      //大小
	int capacity;  //容量
};

typedef struct Heap HP;

void Swap(int* p1, int* p2);
void AdjustDown(int* a, int n, int parent);
void Adjustup(int* a, int child);

                       //数组          数组大小
void HeapInit(HP* php, HPDataType* a, int n);  //初始化
void HeapDestory(HP* php);   //销毁
void HeapPush(HP* php, HPDataType x);  //入一个数据，仍然是堆
void HeapPop(HP* php);   // 删除
HPDataType HeapTop(HP* php);  // 返回堆顶
int HeapSize(HP* php); // 统计大小
bool HEapEmpty(HP* php);  //判断堆是否为空
void HeapPrint(HP* php);  // 打印

Heap.c 部分

#include"Heap.h"


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


void AdjustDown(int* 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[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}

		else  //b情况
		{
			break;
		}

	}
}

void Adjustup(int* 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 HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	/*for (int i = 0;i < n;i++)
	{
		php->a[i] = a[i];
	}*/


	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->size = n;
	php->capacity = n;
	for (int i = (php->size - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(php->a , php->size, i);
	}  

}

void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}

void HeapPush(HP* php, HPDataType x)
{
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;
	Adjustup(php->a, php->size - 1);
 
}

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

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

}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
bool HEapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HeapPrint(HP* php)
{
	for (int i = 0;i < php->size;i++)
	{
		printf("%d ", php->a[i]);

	}
	printf("\n");

	int num = 0;
	int level = 1;
	for (int i = 0;i < php->size;i++)
	{
		printf("%d ", php->a[i]);
		num++;
		if (num == level)
		{
			printf("\n");
			level *= 2;
			num = 0;
		}
	}
	printf("\n");
	printf("\n");
}

 Test.c部分

#include"Heap.h"

int main()
{
	int a[] = { 15,18,28,34,65,19,49,25,37,27 };
	int n = sizeof(a) / sizeof(a[0]);
	HP hp;
	HeapInit(&hp, a, n);
	HeapPrint(&hp);

	HeapPush(&hp, 8);
	HeapPrint(&hp);

	HeapPush(&hp, 888);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapDestory(&hp);

}

演示效果

 数据结构之【堆的实现】

上一篇：实验五 模板类与多态


下一篇：实验5