一、堆的概念及结构
如果有一个关键码的集合 K = {k0 ， k1 ， k2 ， … ， kn-1} ，把它的所有元素按完全二叉树的顺序存储方式存储在一 个一维数组中 ，并满足： Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >=K2i+2) i = 0 ， 1 ， 2… ，则称为小堆 ( 或大堆) 。（即双亲比孩子的数值小(大)——小(大)堆）将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆只有两种，即大堆和小堆，大堆就是父亲结点数据大于儿子结点数据，小堆则反之。
堆的性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。
二、堆的实现
1、结构的定义
由于是堆的元素按完全二叉树的顺序存储方式存储在一位数组中的，所以堆的结构和顺序表的结构一样。
//符号和结构的声明 #define DEF_SIZE 5 #define CRE_SIZE 2 typedef int HPDataType; typedef struct Heap { HPDataType* data; int size; int capacity; }HP;
2、堆的初识化
堆的初识化和顺序表的初始化一样。
//堆的初始化 void HeapInit(HP* php) { assert(php); php->data = (HPDataType*)malloc(sizeof(HPDataType) * DEF_SIZE); if (php->data == NULL) { perror("malloc fail"); exit(-1); } php->size = 0; php->capacity = DEF_SIZE; }
3、堆的插入
堆的插入有两个需要注意的地方：
1、由于堆只会在尾部插入元素，所以我们不需要将 CheckCapacity 单独封装一个函数；
2、由于堆要求在插入元素之后仍保持堆的结构，即保持小根堆/大根堆，所以我们需要对堆进行向上调整，向上调整的过程其实也就是建堆的过程。
//堆的插入--需要保证插入之后仍然保持堆的结构 void HeapPush(HP* php, HPDataType x) { assert(php); //检查容量 if (php->size == php->capacity) { HPDataType* ptr = (HPDataType*)realloc(php->data, sizeof(HPDataType) * php->capacity * CRE_SIZE); if (ptr == NULL) { perror("realloc fail"); exit(-1); } php->data = ptr; php->capacity *= CRE_SIZE; } //插入元素 php->data[php->size] = x; php->size++; //保持堆结构--向上调整 AdjustUp(php->data, php->size - 1); }
4、堆的向上调整
这里我们以小根堆为例，如图：假设现在我们已经有了一个小根堆，现在我们往堆中 (堆尾) 插入一个元素，那么可能会出现两种情况：
1、插入的元素大于父节点，此时我们的堆仍保持小根堆结构，所以不需要改动；比如我们往堆中插入30；
2、插入的元素小于父节点；这种情况又可以分为两种：一是插入的节点虽然小于父节点，但是大于父节点的父节点，这种情况我们只需要交换父节点和该节点，使得堆保存小根堆的结构即可，比如我们插入20；二是该节点不仅小于父节点，还小于父节点的父节点，这种情况下我们就需要把该节点不断往上调整，直到把堆调整为小根堆，最坏的情况是该节点被调整为根节点，比如我们插入10；
//交换两个节点 void Swap(HPDataType* p1, HPDataType* p2) { assert(p1 && p2); HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整--小根堆 void AdjustUp(HPDataType* data, int child) { assert(data); int parent = (child - 1) / 2; //找到父节点 while (child > 0) //当调整到根节点时不再继续调整 { //当子节点小于父节点时交换 if (data[child] < data[parent]) { Swap(&data[child], &data[parent]); //迭代 child = parent; parent = (child - 1) / 2; } //否则直接跳出循环 else { break; } } }
如果我们需要建大根堆，只需要把交换的条件修改一下即可。
//当子节点大于父节点时交换 if (data[child] > data[parent])
5、堆的删除
对于堆的删除有明确的规定：我们只能删除堆顶的元素；但是头删之后存在两个问题：
1、顺序表头删需要挪动数据，效率低下；
2、头删之后堆中各节点的父子关系完全被破坏；
对于上面的这些问题，我们有如下解决办法：
1、我们在删除之前先将堆顶和堆尾的元素交换，然后让size–，这样相当于删除了堆顶的元素，且效率达到了O(1)；
2、由于我们把堆尾元素交换到了堆顶，堆的结构遭到了破坏，所以设计一个向下调整算法来让保持堆的结构；
//删除堆顶的元素--需要保证删除之后仍然保持堆的结构 void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); //首先交换堆顶和堆尾的元素 Swap(&php->data[0], &php->data[php->size - 1]); //删除堆尾的元素 php->size--; //保持堆结构--向下调整 AdjustDown(php->data, php->size, 0); }
6、堆的向下调整
堆向下调整的思路和向上调整刚好相反 (我们还是以小根堆为例)：1、找出子节点中较小的节点；2、比较父节点与子节点，如果父节点大于子节点则交换两个节点；3、交换之后，原来的子节点成为新的父节点，然后继续 1 2 步骤，直到调整为堆的结构
//向下调整 void AdjustDown(HPDataType* data, int n, int parent) { assert(data); int minchild = parent * 2 + 1; //当子节点调整到堆尾时结束循环 while (minchild < n) { //找出较小的子节点 if (minchild + 1 < n && data[minchild + 1] < data[minchild]) { minchild += 1; } //如果父节点大于较小的子节点就交换 if (data[parent] > data[minchild]) { Swap(&data[parent], &data[minchild]); //迭代 parent = minchild; minchild = parent * 2 + 1; } //否则直接跳出循环 else { break; } } }
和向上调整类似，如果我们想要调整为大堆，也只需要改变交换条件：
//找出较大的子节点 if (minchild + 1 < n && data[minchild + 1] > data[minchild]) //如果父节点小于较小的子节点就交换 if (data[parent] < data[minchild])
7、取出堆顶的元素
//取堆顶的元素 HPDataType HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->data[0]; }
8、返回堆的元素个数
//堆的元素个数 int HeapSize(HP* php) { assert(php); return php->size; }
9、判断堆是否为空
//堆的判空 bool HeapEmpty(HP* php) { assert(php); return php->size == 0; }
10、打印堆中的数据
//打印堆中的数据 void HeapPrint(HP* php) { assert(php); int i = 0; for (i = 0; i < php->size; i++) { printf("%d ", php->data[i]); } printf("\n"); }
11、堆的销毁
//堆的销毁 void HeapDestory(HP* php) { assert(php); free(php->data); php->capacity = php->size = 0; }
三、完整代码
1、Heap.h
#pragma once //头文件的包含 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //符号和结构的声明 #define DEF_SIZE 5 #define CRE_SIZE 2 typedef int HPDataType; typedef struct Heap { HPDataType* data; int size; int capacity; }HP; //函数的声明 //堆的初始化 void HeapInit(HP* php); //堆的销毁 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);
2、Heap.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" //堆的初始化 void HeapInit(HP* php) { assert(php); php->data = (HPDataType*)malloc(sizeof(HPDataType) * DEF_SIZE); if (php->data == NULL) { perror("malloc fail"); exit(-1); } php->size = 0; php->capacity = DEF_SIZE; } //堆的销毁 void HeapDestory(HP* php) { assert(php); free(php->data); php->capacity = php->size = 0; } //交换两个节点 void Swap(HPDataType* p1, HPDataType* p2) { assert(p1 && p2); HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整--小根堆 void AdjustUp(HPDataType* data, int child) { assert(data); int parent = (child - 1) / 2; //找到父节点 while (child > 0) //当子节点为根节点时循环结束 { //当子节点小于父节点时交换 if (data[child] < data[parent]) { Swap(&data[child], &data[parent]); //迭代 child = parent; parent = (child - 1) / 2; } //否则直接跳出循环 else { break; } } } //堆的插入--需要保证插入之后仍然保持堆的结构 void HeapPush(HP* php, HPDataType x) { assert(php); //检查容量 if (php->size == php->capacity) { HPDataType* ptr = (HPDataType*)realloc(php->data, sizeof(HPDataType) * php->capacity * CRE_SIZE); if (ptr == NULL) { perror("realloc fail"); exit(-1); } php->data = ptr; php->capacity *= CRE_SIZE; } //插入元素 php->data[php->size] = x; php->size++; //保持堆结构--向上调整 AdjustUp(php->data, php->size - 1); } //向下调整 void AdjustDown(HPDataType* data, int n, int parent) { assert(data); int minchild = parent * 2 + 1; //当子节点调整到堆尾时结束循环 while (minchild < n) { //找出较小的子节点 if (minchild + 1 < n && data[minchild + 1] < data[minchild]) { minchild += 1; } //如果父节点大于较小的子节点就交换 if (data[parent] > data[minchild]) { Swap(&data[parent], &data[minchild]); //迭代 parent = minchild; minchild = parent * 2 + 1; } //否则直接跳出循环 else { break; } } } //删除堆顶的元素--需要保证删除之后仍然保持堆的结构 void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); //首先交换堆顶和堆尾的元素 Swap(&php->data[0], &php->data[php->size - 1]); //删除堆尾的元素 php->size--; //保存堆结构--向下调整 AdjustDown(php->data, php->size, 0); } //取堆顶的元素 HPDataType HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->data[0]; } //堆的元素个数 int HeapSize(HP* php) { assert(php); return php->size; } //堆的判空 bool HeapEmpty(HP* php) { assert(php); return php->size == 0; } //打印堆中的数据 void HeapPrint(HP* php) { assert(php); int i = 0; for (i = 0; i < php->size; i++) { printf("%d ", php->data[i]); } printf("\n"); }
3、test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" int main() { int a[] = { 27,15,19,18,28,34,65,49,25,37 }; HP hp; //堆的初始化 HeapInit(&hp); //插入元素 int i = 0; int len = sizeof(a) / sizeof(a[0]); for (i = 0; i < len; i++) { HeapPush(&hp, a[i]); } HeapPrint(&hp); //删除堆顶元素 HeapPop(&hp); HeapPrint(&hp); //取出堆顶元素 HPDataType top = HeapTop(&hp); printf("%d\n", top); //堆排序 for (i = 0; i < len - 1; i++) { printf("%d ", HeapTop(&hp)); HeapPop(&hp); } //堆的销毁 HeapDestory(&hp); return 0; }
大家也可以去我的 Gitee 仓库中获取完整代码：Heap/Heap · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
