三、堆（堆的概念及结构）
🍁概念
🍔普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
🍔小堆：
🍔大堆：
🍁堆的性质：
⭕堆中某个节点的值总是不大于或不小于其父节点的值。
⭕堆总是一棵完全二叉树。
🍁堆的实现
💧 堆向下调整算法
🥝现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
⭕代码实现：
void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; // 通过父亲节点找到孩子 while (child < n) // 当孩子节点超过了数组的大小那么就跳出循环 { if (child < n - 1 && a[child] < a[child + 1]) //找到孩子中最大的那个 { child++; } if (a[child] > a[parent]) // 最大的跟父亲比较，大于（小于）父亲了就交换位置 { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { return; } } }
💧堆的创建
🥝 下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
💧 堆的插入
🥝 先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。
⭕代码实现：
void AdjustUp(HPDataType* 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 { return; } } } void HeapPush(HP* php, HPDataType x) { assert(php); //防止传入的是空指针 if (php->capacity == php->size) //当空间不够用了，扩展空间 { int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2); HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType)); if (tmp == NULL) //判断是否扩展成功 { perror("realloc fail"); // 失败返回错误信息 return; } php->a = tmp; //初始化扩展好的空间 php->capacity = newcapacity; } php->a[php->size] = x; php->size++; AdjustUp(php->a, php->size - 1); // 向上调整数据 }
💧 堆的删除
🥝删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
🔴将堆顶元素与堆中最后一个元素进行交换
🔴除堆中最后一个元素
🔴将堆顶元素向下调整到满足堆特性为止
⭕代码实现：
void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; // 通过父亲节点找到孩子 while (child < n) // 当孩子节点超过了数组的大小那么就跳出循环 { if (child < n - 1 && a[child] < a[child + 1]) //找到孩子中最大的那个 { child++; } if (a[child] > a[parent]) // 最大的跟父亲比较，大于（小于）父亲了就交换位置 { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { return; } } } void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); swap(&php->a[php->size-1], &php->a[0]); php->size--; AdjustDown(php->a, php->size, 0); }
堆的全部代码
✅Heap.h 文件（头文件）
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int HPDataType; //定义堆的类型 typedef struct Heap //创建堆的初始结构 { HPDataType* a; int size; int capacity; }HP; //向上调整数据 void AdjustUp(HPDataType* a, int child); //向下调整数据 void AdjustDown(int* a, int n, int parent); //初始化堆 void HeapInit(HP* php); //堆的销毁 void HeapDestroy(HP* php); //向堆中插入数据 void HeapPush(HP* php, HPDataType x); //删除堆顶的数据 void HeapPop(HP* php); //弹出堆顶的数据 HPDataType HeapTop(HP* php); //判断是否为空堆 bool HeapEmpty(HP* php); //计算堆的大小 int HeapSize(HP* php);
✅Heap.c 文件
#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" //交换堆中指定的两个数据 void swap(HPDataType* x, HPDataType* y) { HPDataType tmp = *x; *x = *y; *y = tmp; } //向上调整数据 void AdjustUp(HPDataType* 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 { return; } } } //向下调整数据 void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child < n - 1 && a[child] < a[child + 1]) { child++; } if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { return; } } } //初始化堆 void HeapInit(HP* php) { assert(php); php->a = NULL; php->capacity = 0; php->size = 0; } //堆的销毁 void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->capacity = 0; php->size = 0; } //向堆中插入数据 void HeapPush(HP* php, HPDataType x) { assert(php); if (php->capacity == php->size) { int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2); HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType)); if (tmp == NULL) { perror("realloc fail"); return; } php->a = tmp; php->capacity = newcapacity; } php->a[php->size] = x; php->size++; AdjustUp(php->a, php->size - 1); } //删除堆顶的数据 void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); swap(&php->a[php->size - 1], &php->a[0]); php->size--; AdjustDown(php->a, php->size, 0); } //弹出堆顶的数据 HPDataType HeapTop(HP* php) { assert(php); return php->a[0]; } //判断是否为空堆 bool HeapEmpty(HP* php) { return php->size == 0; } //计算堆的大小 int HeapSize(HP* php) { return php->size; }
✅Test.c文件
#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" int main() { HP hp; HeapInit(&hp); int a[] = { 65,100,70,32,50,60 }; for (int i = 0; i < sizeof(a) / sizeof(int); ++i) { HeapPush(&hp, a[i]); } while (!HeapEmpty(&hp)) { int top = HeapTop(&hp); printf("%d\n", top); HeapPop(&hp); } return 0; }
🥰 运行结果如下产生了一个大堆
