数据结构|数据结构之堆的模拟实现 php|数据结构

【数据结构|数据结构之堆的模拟实现】
堆的模拟实现

堆的初始化
堆的销毁
堆的打印
堆的插入
堆的删除
获取堆顶的数据
获取堆的元素个数
堆的判空

堆的初始化首先，先创建这个堆的结构体，其中有存储数据的数组，存储元素的个数和最大容量。

typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP;

接着对堆进行初始化，我们先开辟一个空间将其数组中的元素赋值拷贝到堆中，然后进行堆的初始化。

void HeapInit(HP* php, HPDataType* a, int n) { 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 = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDown(php->a, php->size, i); } }

堆的销毁每开辟一个空间在结束后都要销毁其内存空间。

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

堆的打印每一个元素遍历并打印。

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

堆的插入在堆中插入数据时，由于我们要将元素插入到二叉树的最后一个节点的位置，所以为了保证堆的成立，我们要先进行一个向上调整算法。

void AdjustUp(int* a,int child) { int parent = (child - 1) / 2; while (child > 0) {if (child > parent) {swap(a[child], a[parent]); child = parent; parent = (child - 1) / 2; } else {break; } } }

接着进行堆的插入

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; AdjustUp(php->a,php->size - 1); } }

堆的删除堆的删除是删除堆顶的元素，但我们不能直接删除，我们要先将堆顶的元素和尾端元素交换位置，再删除尾端元素，最后进行向下调整算法和堆排序的思想类似。
原因：如果我们直接删除堆顶的元素，会使堆的父子关系被打乱，需要重新建堆，时间复杂度为N，而如果先交换的话，时间复杂度为logn。