💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃
文章目录
一、堆的概念
堆(Heap)是计算机科学中一类特殊的数据结构的统称。如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。除了最后一层以外上面的节点但是非空的，最后一层节点是从左到右依次排布的）
二、堆的性质
🔸 非线性，完全二叉树。适合用数组存储。
🔸堆是无序的，也就是左右可以互换
🔸最值总在 0 号位
根据这个特点我们就可以做很多事情，比如TopK问题 (在一堆数据里面找到前 K 个最大 / 最小的数).
比如点餐软件中有上千家店铺，，我想选出该地区好评最多的十家川菜店，我们不用对所有数据排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。
三、堆的分类
1.大根堆 2.小根堆
1.大根堆
定义：树中的任意一个双亲节点都大于等于孩子节点。
2.小根堆
定义：树中的任意一个双亲节点都小于等于孩子节点。
四、说明
以下的方法均以小堆来推理，如果想实现大堆，则修改【<】符号等方式实现。
五、堆的结构
typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP;
🚩六、堆的向上调整
向上调整的前提是，调整位置之前必须是堆。如果目的是调成小堆，则要保证调整位置之前是小堆；如果目的是调成大堆，则要保证调整位置之前是大堆。
1.图示
2.代码实现
//向上调整 void AdjustUp(HPDataType* a, int child) { //传入数组，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 return; } }
⌚️3.时间复杂度分析
时间复杂度：O（logN）
最坏情况：调整到根;
最好情况：不用调整，
📌七、堆的向下调整
向下调整的前提是，左右子树必须是小堆或者大堆。
1.思路：
如图：
此案例是要调整根节点40开始向下调整，首先确保根节点的左右子树是小堆（由图得成立）。
1.parent的两个孩子进行比较，选出小的。
2.进行交换
3.child>n结束
2.代码实现
//向下调整 void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; //一直交换到数的最后，也就是数组的最后一个位置 while (parent<n) { if (child + 1 < n && a[child + 1] < a[child]) { child++; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); // 继续往下调整 parent = child; child = parent * 2 + 1; } else { return; } } }
⌚️3.时间复杂度分析
时间复杂度：O（logN）
最坏情况：调整到根;
最好情况：不用调整，
八、删除根
1.思路：
1.先将根与最后一个节点交换，
2.删除最后一个节点；
3.进行向下调整。
2.代码实现
void HeapPop(HP* p) { assert(p); assert(p->size > 0); Swap(&p->a[0], &p->a[p->size - 1]); --p->size; AdjustDown(p->a, p->size, 0); }
⌚️3.时间复杂度分析
时间复杂度：O:N(logN)
九、创建堆
创建堆的思路可以通过向上调整，也可通过向下调整。这里讲通过向上调整建立堆。
由于我的AdjustUp函数是用来调整小堆的，所以，这里创建的也是小堆。
1.思路：
传入参数
a：数组，n：是数组元素个数
1.为p->a开辟n个空间；
2.利用memcpy函数，把数组a复制到p->a中
3.在使用AdjustUp调整，从1-n-1逐步向下延伸；
2.代码实现
//建立小堆 void HeapInitArray(HP* p, int* a, int n) { //a：数组，n：是数组元素个数 assert(p); assert(a); p->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (p->a == NULL) { perror("malloc fail"); exit(-1); } p->size = n; p->capacity = n; //把传入数组a复制到p->a中 memcpy(p->a, a, sizeof(HPDataType) * n); // 向上调整，调整成一个小堆 for (int i = 1; i < n; i++) { AdjustUp(p->a, i); } }
十、所有方法实现汇总
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" //初始化 void HeapInit(HP* p) { assert(p); p->a = NULL; p->size = 0; p->capacity = 0; } //销毁 void HeapDestroy(HP* p) { assert(p); free(p->a); p->a = NULL; p->size = p->capacity = 0; } //插入数据 void HeapPush(HP* p, HPDataType x) { //从最后一个位置插入 assert(p); //扩容 if (p->capacity == p->size) { //如果刚开始数组为空，就开辟4个空间。如果不为空，以后每次扩大2倍。 int newcapacity = p->capacity==0 ? 4 : p->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * p->capacity); if (tmp == NULL) { perror("realloc fial\n"); exit(-1); } p->a = tmp; p->capacity = newcapacity; } p->a[p->size] = x; p->size++; AdjustUp(p->a, p->size-1); } //交换 void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整 void AdjustUp(HPDataType* a, int child) { //传入数组，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 return; } } //向下调整 void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; //一直交换到数的最后，也就是数组的最后一个位置 while (parent<n) { if (child + 1 < n && a[child + 1] < a[child]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); // 继续往下调整 parent = child; child = parent * 2 + 1; } else { return; } } } //打印二叉树 void HeapPrint(HP* php) { assert(php); for (size_t i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); } //建立小堆 void HeapInitArray(HP* p, int* a, int n) { //a：数组，n：是数组元素个数 assert(p); assert(a); p->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (p->a == NULL) { perror("malloc fail"); exit(-1); } p->size = n; p->capacity = n; //把传入数组a复制到p->a中 memcpy(p->a, a, sizeof(HPDataType) * n); // 向上调整，调整成一个小堆 for (int i = 1; i < n; i++) { AdjustUp(p->a, i); } } //删除根 void HeapPop(HP* p) { assert(p); assert(p->size > 0); Swap(&p->a[0], &p->a[p->size - 1]); --p->size; AdjustDown(p->a, p->size, 0); } //获取根 HPDataType HeapTop(HP* p) { assert(p); assert(p->size > 0); return p->a[0]; } //判空 bool HeapEmpty(HP* p) { assert(p); return p->size == 0; }
