如果我每天都找出所犯错误和坏习惯，那么我身上最糟糕的缺点就会慢慢减少。这种自省后的睡眠将是多么惬意啊。
目录
🎄堆的概念及结构：
🎄堆的实现：
✔基本接口函数：
✔结构体：
✔HeapInit函数：
✔HeapDestory函数：
✔HeapPrint函数：
✔HeapPush函数：
✔HeapPop函数：
✔HeapTop函数：
🎄完整代码：
✔Heap.h:
✔Heap.c:
✔Text.c:
🎄堆的概念及结构：
如果有一个关键码的集合K = { k0，k1 ，k2 ，…，k(n-1) }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K(2*i+1)且 Ki <= K(2*i+2) (Ki >= K(2*i+1)且Ki >= K(2*i+2)) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值
- 堆总是一棵完全二叉树
- 简单来说：
- 父节点都比其的子节点大的完全二叉树叫做大堆。
- 父节点都比其的子节点小的完全二叉树叫做小堆。
如图：
🎄堆的实现：
✔基本接口函数：
//堆的初始化 void HeapInit(HP* hph); //堆的销毁 void HeapDestory(HP* hph); //堆的打印 void HeapPrint(HP* hph); // 堆的插入 void HeapPush(HP * hph, HPDataType x); // 堆的删除 void HeapPop(HP* hph); // 取堆顶的数据 HPDataType HeapTop(HP* hph); // 堆的数据个数 int HeapSize(HP* hph); // 堆的判空 int HeapEmpty(HP* hph);
✔结构体：
typedef int HPDataType; typedef struct heap { HPDataType* a; int capacity; int size; }HP;
✔HeapInit函数：
//堆的初始化 void HeapInit(HP* hph) { assert(hph); hph->a = NULL; hph->capacity = hph->size = 0; }
✔HeapDestory函数：
//堆的销毁 void HeapDestory(HP* hph) { assert(hph); free(hph->a); hph->a = NULL; hph->capacity = 0; hph->size = 0; }
✔HeapPrint函数：
//堆的打印 void HeapPrint(HP* hph) { for (int i = 0; i < hph->size; ++i) { printf("%d ", hph->a[i]); } printf("\n"); }
✔HeapPush函数：
当capacity==size时扩容（包括初始化的方案），当size==0时，扩容4个空间，否则扩容二倍的空间，capacity也跟着扩大，当push后size++。
Swap交换函数：
void Swap(HPDataType* p1, HPDataType* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; }
//向上调整 //child和parent都是下标 void AdjusUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child>0) { if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } // 堆的插入 void HeapPush(HP* hph, HPDataType x) { assert(hph); //扩容 if (hph->capacity == hph->size) { int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2; HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail:"); exit(-1); } hph->a = tmp; hph->capacity = newcapacity; } hph->a[hph->size] = x; hph->size++; //向上调整 AdjusUp(hph->a, hph->size - 1); }
✔HeapPop函数：
出堆顶的元素，让第一个位置的值和最后一个位置的值交换，再size--就相当于删除了，但交换上去的值在根节点的位置上，我们无法维持是大堆的情况，因此还需要向下调整Ajustdown。
//向下调整 void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1< n && a[child] < a[child + 1]) { child = child + 1; } //child 大于 parent 就交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } // 堆的删除 void HeapPop(HP* hph) { assert(hph); assert(!HeapEmpty(hph)); Swap(&hph->a[0], &hph->a[hph->size - 1]); hph->size--; AdjustDown(hph->a, hph->size, 0); }
✔HeapTop函数：
// 取堆顶的数据 HPDataType HeapTop(HP* hph) { assert(hph); assert(hph->size > 0); return hph->a[0]; }
🎄完整代码：
✔Heap.h:
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <assert.h> #include <stdbool.h> #include <stdlib.h> typedef int HPDataType; typedef struct heap { HPDataType* a; int capacity; int size; }HP; //堆的初始化 void HeapInit(HP* hph); //堆的销毁 void HeapDestory(HP* hph); //堆的打印 void HeapPrint(HP* hph); // 堆的插入 void HeapPush(HP * hph, HPDataType x); // 堆的删除 void HeapPop(HP* hph); // 取堆顶的数据 HPDataType HeapTop(HP* hph); // 堆的数据个数 int HeapSize(HP* hph); // 堆的判空 int HeapEmpty(HP* hph);
✔Heap.c:
#define _CRT_SECURE_NO_WARNINGS 1 #include "heap.h" //堆的打印 void HeapPrint(HP* hph) { for (int i = 0; i < hph->size; ++i) { printf("%d ", hph->a[i]); } printf("\n"); } //堆的初始化 void HeapInit(HP* hph) { assert(hph); hph->a = NULL; hph->capacity = hph->size = 0; } //堆的销毁 void HeapDestory(HP* hph) { assert(hph); free(hph->a); hph->a = NULL; hph->capacity = 0; hph->size = 0; } void Swap(HPDataType* p1, HPDataType* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下调整 //child和parent都是下标 void AdjusUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child>0) { if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } // 堆的插入 void HeapPush(HP* hph, HPDataType x) { assert(hph); //扩容 if (hph->capacity == hph->size) { int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2; HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail:"); exit(-1); } hph->a = tmp; hph->capacity = newcapacity; } hph->a[hph->size] = x; hph->size++; //向下调整 AdjusUp(hph->a, hph->size - 1); } //向上调整 void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1< n && a[child] < a[child + 1]) { child = child + 1; } //child 大于 parent 就交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } // 堆的删除 void HeapPop(HP* hph) { assert(hph); assert(!HeapEmpty(hph)); Swap(&hph->a[0], &hph->a[hph->size - 1]); hph->size--; AdjustDown(hph->a, hph->size, 0); } // 取堆顶的数据 HPDataType HeapTop(HP* hph) { assert(hph); assert(hph->size > 0); return hph->a[0]; } // 堆的数据个数 int HeapSize(HP* hph) { assert(hph); return hph->size; } // 堆的判空 int HeapEmpty(HP* hph) { assert(hph); return hph->size == 0; }
✔Text.c:
#define _CRT_SECURE_NO_WARNINGS 1 #include "heap.h" void Heap() { int arry[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 }; HP hph; HeapInit(&hph); HeapPrint(&hph); for (int i = 0; i < sizeof(arry) / sizeof(int); i++) { HeapPush(&hph, arry[i]); } HeapPrint(&hph); HeapPush(&hph, 100); HeapPrint(&hph); HeapPop(&hph); HeapPrint(&hph); HeapDestory(&hph); } void TestHeap2() { int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 }; HP hp; HeapInit(&hp); for (int i = 0; i < sizeof(array) / sizeof(int); ++i) { HeapPush(&hp, array[i]); } while (!HeapEmpty(&hp)) { printf("%d ", HeapTop(&hp)); HeapPop(&hp); } HeapDestroy(&hp); } int main() { TestHeap2(); return 0; }
