通过前几次的博客我们大致了解了堆的性质,接下来我们用数据结构来封装堆
注意本篇博客建堆建的是大堆。
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); }
演示效果