【数据结构】堆的创建

Heap.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//创建堆结构体
typedef int HPDateType;
typedef struct Heap
{HPDateType* a;int size;int capacity;
}HP;//堆的初始化
void HPInit(HP* php);//堆的销毁
void HPDestroy(HP* php);//交换
void Swap(HPDateType* p1, HPDateType* p2);//向上调整
void AdjustUp(HPDateType* a, int child);//堆的插入
void HPPush(HP* php, HPDateType x);//向下调整
void AdjustDown(HPDateType* a, int n, int parent);//堆的删除(删除根部数据)
void HPPop(HP* php);//取堆顶的数据
HPDateType HPTop(HP* php);//堆的数据个数
int HPSize(HP* php);//判断堆是否为空
bool HPEmpty(HP* php);

Heap.c

#include"Heap.h"//堆的初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}//堆的销毁
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;free(php);php = NULL;
}//交换
void Swap(HPDateType* p1, HPDateType* p2)
{HPDateType* tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上调整
void AdjustUp(HPDateType* a, int child)
{int parent = (child - 1) / 2;//小堆（根为最小值）while (parent >= 0 && child != 0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}大堆（根为最小值）//while (parent >= 0 && child != 0)//{//	if (a[parent] < a[child])//	{//		Swap(&a[parent], &a[child]);//		child = parent;//		parent = (child - 1) / 2;//	}//	else//	{//		break;//	}//}
}//堆的插入
void HPPush(HP* php, HPDateType x)
{assert(php);//开辟空间if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDateType* tmp = (HPDateType*)realloc(php->a, sizeof(HPDateType) * newcapacity);if (tmp == NULL){perror("realloc fail:");exit(1);}php->a = tmp;php->capacity = newcapacity;}//添加数据php->a[php->size++] = x;//向上调整建堆AdjustUp(php->a, php->size - 1);
}//向下调整
void AdjustDown(HPDateType* a, int n, int parent)
{int child = parent * 2 + 1;//小堆while (child < n){if (child + 1 < n && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = (parent + 1) * 2;}else{break;}}大堆//while (child < n)//{//	if (child + 1 < n && a[child] < a[child + 1])//	{//		child++;//	}//	if (a[parent] < a[child])//	{//		Swap(&a[parent], &a[child]);//		parent = child;//		child = (parent + 1) * 2;//	}//	else//	{//		break;//	}//}
}//堆的删除(删除根部数据)
void HPPop(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);
}//取堆顶的数据
HPDateType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[php->size - 1];
}//堆的数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return HPSize(php);
}