概述
目录
1.堆的引入
(1)完全二叉树概念
(2)堆的概念
(3)堆的示意图
[1]小堆示意图
[2]大堆示意图
2.堆的特殊情况
(1)堆的向下调整算法
(2)堆的向上调整算法
3.堆的局部实现
(1)堆的功能分析
(2)堆的具体实现
[1]堆结点创建
[2]堆的交换函数
[3]堆的向下调整函数
[4]堆的向上调整函数
[5]堆结构创建函数
[6]堆的容量检测扩容函数
[7]堆中插入结点
[8]堆顶元素的删除
[9]获取堆顶元素
[10]获取堆的元素个数
[11]判断堆是否是空
[12]删除整个堆
4.堆的整体实现代码
堆在数据结构中很常用，本文将用大量的图片来帮助读者理解堆，特别是理解堆的调整算法。(本文代码均使用C语言，在win10系统下的vs2019验证)
1.堆的引入
(1)完全二叉树概念
满二叉树：二叉树中每个非叶子结点都有两个非空的孩子结点。
完全二叉树：和满二叉树相比，完全二叉树从上往下数，第一层至倒数第二层和满二叉树一样都是满的。完全二叉树的最下层可以不满，但是从左到右必须是连续的，中间不可以间断。(看第二行第二幅图)
非完全二叉树：不满足完全二叉树性质的均是非完全二叉树。
如图：
(2)堆的概念
堆是完全二叉树的一种，在完全二叉树的基础上加以条件限制，就成为了堆。
那么给完全二叉树增加什么限制就会成为堆？
限制分两种：[1]保证每个结点的值不比它的双亲结点小，称为大根堆（最大堆或大堆）；[2]保证每个结点不比它的双亲结点大，称为小根堆（最小堆或小堆）。
本文总体代码是实现小堆，只要理解了小堆，大堆的实现也是轻而易举的。(只需要将和比较结点大小的代码修改一下，即可从小堆转换为大堆)。
(3)堆的示意图
[1]小堆示意图
小堆：每个结点的值不大于它的双亲结点。
如下图：
[2]大堆示意图
大堆：每个结点的值不小于它的双亲结点。
如下图：
2.堆的特殊情况
为什么要先看堆的特殊情况？
因为堆的整体实现需要在特殊情况的基础上进行。在这里理解了特殊情况后，在堆的实现中就会更容易理解。
(1)堆的向下调整算法
堆的向下调整算法应用于创建堆结构和删除堆顶元素中。什么情况下需要用到向下调整算法？
如下图一这种情况。可以看到图一中，根结点27的左右子树均是小堆结构，可是以27为根结点的树整体却不是小堆结构，这就是特殊情况：
如何解决特殊情况？当然是调整根结点位置。
如何调整根结点位置？只能把根结点向下调整。这也是向下调整算法名字的由来。
如何向下调整？找出待调整结点(27)最小的孩子结点，并与待调整结点进行交换。如图二所示：
将两个结点交换后发现，目前以27为根的这棵子树又遇到上面这种特殊情况：以27为双亲结点的两棵子树均是小堆，但以27为根的这棵子树却不是小堆结构。也就是说，子树的小堆结构可能被破坏。那么就只能继续进行向下调整，如图三图四所示：
经过图四的调整后，得到的结果如下图五：
观察图五发现，目前以27为根结点的这棵子树依旧不满足小堆结构，那么继续向下调整呗。继续调整后满足小堆结构，如图六图七：
在这个算法中可以发现，首次向下调整后很可能破坏根结点子树的小堆结构，所以需要不断地向下比较，不满足性质就要调整。说明在代码实现中，我们需要使用循环结构，通过循环结构，让这个调整过程不断向下进行下去，直到让整棵树满足小堆结构。
(2)堆的向上调整算法
堆的向上调整算法用于堆的插入函数中。小堆中插入一个元素后破坏了堆的结构，使用向上调整算法来使得二叉树又形成小堆结构。
如下图一是小堆：
在小堆中插入一个元素10，注意，只能将新结点插到最后一个位置。如图二：
可以看到图二中插入后目前的二叉树显然不满足小堆结构。因为新结点做为28的子结点，却比28小，显然不满足小堆。因此需要调整新结点的位置。
那么新结点的位置往哪里调整？自然只能向上调整了。这也是向上调整算法名字的由来。
这里要强调，图一中是小堆，所以每个结点的值都不大于它的双亲结点。
调整新结点时，比较新结点和新结点的双亲结点的大小。如果新结点大于双亲结点，说明满足小堆，自然不需要改变了。但目前新结点(10)小于双亲结点(28)，因此需要交换新结点和双亲结点。如图三：
将新结点和它的双亲结点交换后，经过比较后发现此时的新结点(10)仍旧小于它的双亲结点(18)，因此继续向上调整。如图四：
图四交换后发现结果仍旧不满足小堆结构，因此继续向上调整，如图五六七：
可以发现向上调整算法中，第一次调整后，并不一定会满足小堆结构，因此需要一直向上比较并调整，所以在函数的具体实现中也需要使用循环结构使得新结点不断向上调整。
3.堆的局部实现
(1)堆的功能分析
堆中都需要实现什么功能？
1.创建堆结构的函数。
2.堆的向上调整算法
3.堆的向下调整算法
4.堆顶元素的删除
5.堆的销毁
6.给堆中新插入结点
7.交换两个结点值的函数
8.获取堆中结点个数的函数
9.堆的容量检测与扩容函数。(因为我们用数组存储堆的元素，而数组空间有限，所以当空间不足时就需要进行扩容)
(2)堆的具体实现
[1]堆结点创建
堆是一种数据结构，而堆结点则是该结构中存储元素的东西。C语言中，我们应该将堆结点设置为结构体类型。
结构体中可能存放多种类型的数据，所以我们可以用typedef关键字给数据类型取个别名，这样如果需要修改存储的元素类型就只需要在这里修改就可以了。
typedef int DataType;堆结点结构体中，我们需要定义的元素有：DataType类型的指针，用来指向一段DataType类型的数组空间；int 类型的capacity变量，用来保存数组空间的容量；int 类型的size变量，用来保存这段数组空间中存储的元素的个数。
同时为了使用方便，我们也用typedef关键字给结构体类型起别名Heap(这个别名起什么都可以，只要不是关键字就行)。这样使用时会方便很多。
typedef struct Heap {
//定义DataType类型的指针
//用来指向一段连续的数组空间
DataType* array;
//array指向的数组空间的容量
int capacity;
//array指向的数组空间内存储的元素个数
int size;
}Heap;[2]堆的交换函数
在堆的调整算法中提到过需要交换两个结点的元素，因此需要定义交换函数。这里需要传递指针，用指针来实现交换。
//交换堆中两个结点保存的值
void Swap(DataType* left, DataType* right) {
DataType temp = *left;
*left = *right;
*right = temp;
}[3]堆的向下调整函数
向下调整函数的工作流程在上面已经用图片了解了，现在来看一下实现原理。
这里传递的参数是双亲结点的下标，根据这个下标求出左孩子的下标。只要左孩子的下标比结点的个数小，说明孩子下标并没有越界。
在循环体中，我们先要找出左孩子与右孩子中的最小值。首先判断右孩子是否存在，存在的话与左孩子比较大小。找出最小的孩子结点。
找出最小的孩子结点后，将孩子结点和双亲结点进行比较。如果孩子结点小于双亲结点，说明不满足小堆，需要调整。
调整时需要先交换双亲结点和孩子结点的值，然后更新双亲结点和孩子结点的下标，让循环体继续向下调整修复在交换过程中被破坏的下层结构。
//堆的向下调整
//parent是双亲结点下标
//这里的child parent都是下标
void AdjustDown(Heap* hp, int parent) {
//标记左孩子的下标，因为可能只有左孩子没有右孩子
int child = parent * 2 + 1;
int size = hp->size;
//只要孩子结点的下标小于总结点的个数
//说明并没有越界
while (child < size) {
//找出两个孩子中最小的那个
//child+1<size 成立时说明右孩子结点存在
//hp->array[child + 1] < hp->array[child] 这个表达式成立说明右孩子比左孩子小
//那么child下标就要转移到右孩子
if (child + 1 < size && hp->array[child + 1] < hp->array[child])
child += 1;
//判断双亲结点是否比最小的孩子结点小
if (hp->array[child] < hp->array[parent]) {
Swap(&hp->array[parent], &hp->array[child]);
parent = child;
child = parent * 2 + 1;
}
else {
return;
}
}
}[4]堆的向上调整函数
向上调整函数其实和向下调整函数差不多。
向上调整函数的参数是孩子结点的下标，通过孩子结点的下标找出它的双亲结点下标。只要双亲结点下标不是0，说明还没有调整到根结点。
循环体中，比较孩子结点和双亲结点的大小，如果孩子结点小于双亲结点，说明不满足小堆结构，需要交换孩子结点和双亲结点的值，然后更新下标，让循环体继续向上调整。
//堆的向上调整
void AdjustUp(Heap* hp, int child) {
//parent是child结点的双亲结点的下标
int parent = (child - 1) / 2;
//循环是为了一直向上调整
//child下标不等于0说明还没有调整到根节点
while (child) {
//如果孩子结点的值小于双亲结点的值
//说明不满足小堆
if (hp->array[child] < hp->array[parent]) {
//交换孩子与双亲的值
//并且把孩子的下标和双亲的下标更新使得满足循环条件继续向上调整
Swap(&hp->array[parent], &hp->array[child]);
child = parent;
parent = (child - 1) / 2;
}
//满足小堆就可以退出了
else {
return;
}
}
}[5]堆结构创建函数
这里举的例子是用数组元素构成大堆。
创建堆结构时，我们首先要先把传入的数组中的元素都存储在二叉树中。如图一：
但这样的二叉树显然不满足大堆的性质。如何解决？用向下调整。
可是这个二叉树完全是混乱无序的，根节点的两个子树都不是大堆结构。我们在上面只看了特殊情况的向下调整，那么如何应对混乱无序的二叉树？
对于混乱无序的二叉树其实很简单，咱们先看最后一个非叶子结点(3)。如果只看以它为根的这棵子树，这是不是就成了大堆的特殊情况？子节点(6)大于双亲结点(3)，以3为根的这棵子树不满足大堆。而以子节点(6)为根的二叉树只有一个元素，那么我们就可以认为以子结点(6)为根的这棵二叉树是大堆，这样是不是就成了特殊情况？
所以解决混乱无序的方法是：从最后一个非叶子结点开始，依次把以非叶子结点为根的二叉树看作特殊情况去解决。如图二三四：
但是根据上面的方法遇到了问题，虽然已经调整到根节点，却发现仍旧不满足大堆结构，如图五：
这是因为在向上调整的过程中，如果一旦和上层的结点发生交换，可能会破坏下层的堆结构。这个在讲解向下调整算法的时候在结尾提到了。如何解决？在每一次调用向下调整算法后，在调整算法中不断通过循环向下去修复被破坏的堆结构。如图六七：
//堆的创建
void HeapCreate(Heap* hp, DataType _array[], int _size) {
//assert检查指针hp是否存在
//当指针hp指向空，就会报错
assert(hp);
//根据传递的参数_size来为hp开辟指向的空间
//如果开辟失败，malloc函数会返回NULL，hp就会指向NULL
hp->array = (DataType*)malloc(_size * sizeof(DataType));
//判断空间是否开辟成功
if (hp->array == NULL) {
assert(0);
return;
}
//空间开辟成功，修改堆中的容量
hp->capacity = _size;
//空间开辟成功，开始存入元素
for (int i = 0; i < _size; i++) {
hp->array[i] = _array[i];
}
//修改堆中元素个数
hp->size = _size;
//开始从最后一个非叶子结点进行向下调整
//(hp->size - 2)/2 这是最后一个非叶子结点的下标
for (int i = (hp->size - 2) / 2; i >= 0; i--) {
AdjustDown(hp,i);
}
}[6]堆的容量检测扩容函数
这个函数的作用是：在往堆结构中插入元素时，需要判断存储堆元素的数组容量是否足够，如果不够就需要先扩容再插入元素。
//检查堆中空间是否足够，不够要扩容
void HeapCheckCapacity(Heap* hp) {
assert(hp);
//当容量和元素个数相同说明空间满了
if (hp->capacity == hp->size) {
//newCapacity就是准备新申请的空间大小
int newCapacity = hp->capacity * 2;
//申请新空间
DataType* temp = (DataType*)malloc(sizeof(DataType) * newCapacity);
//判断空间是否成功申请
//申请失败的话malloc函数会返回NULL
if (temp == NULL) {
assert(0);
return;
}
//将原空间的元素复制到新空间
for (int i = 0; i < hp->size; i++) {
temp[i] = hp->array[i];
}
//释放原空间
free(hp->array);
//将指针指向新空间
hp->array = temp;
//更新容量
hp->capacity = newCapacity;
}
}[7]堆中插入结点
这个函数就是往堆中插入新结点，需要调用容量检测扩容函数，当容量不足就要扩容。插入完成后，就需要将新结点向上调整，使整棵树满足堆结构。
//给堆中插入元素
void HeapPush(Heap* hp, DataType data) {
//首先要检测容量
HeapCheckCapacity(hp);
hp->array[hp->size] = data;
hp->size++;
//这里就需要向上调整了，因为插入元素后可能会破坏堆的结构
//hp->size - 1 是新结点的下标
AdjustUp(hp, hp->size - 1);
}[8]堆顶元素的删除
堆中的删除操作只有两种，删除堆顶元素，删除整个堆。不可以单独删除除堆顶外的元素。
堆顶元素的删除如何实现？
自然不可以直接删除，不然就变成了两颗子树。我们需要把堆顶元素和堆最末尾的结点值交换。然后将堆的元素减一，这样是不是使用或访问时，就会少一个元素。
可是这样有一个问题，会出现根结点的两个子树满足性质，但整棵树不满足，也就是特殊情况中介绍的第一种，这里就要用到向下调整了。
如图一是小堆，需要删除堆顶结点：
首先交换堆顶元素和最后一个元素，然后将size变量个数减一(因为size中存储结点个数，减1后最后一个结点就访问不到了，相当于删除了)，如图二三四：
经过上面的步骤虽然删除了堆顶结点，但是破坏了小堆结构，造成了特殊情况，因此需要使用向下调整算法修复堆结构。在向下调整的过程中，我们发现会破坏下层的堆结构，所以需要在调整算法中循环修复下层堆结构。如图五六七：
//删除堆顶元素
void HeapPop(Heap* hp) {
//判断hp指针是否指向空，指向空就不能进行删除操作
if (HeapEmpty(hp)) {
return;
}
//交换堆顶元素和最后一个结点的元素
Swap(&hp->array[0], &hp->array[hp->size-1]);
hp->size--;
//从堆顶进行向下调整
AdjustDown(hp,0);
}[9]获取堆顶元素
这个函数非常简单，堆顶元素就在数组0下标处存储，因此只需要返回0下标的元素即可。
//返回堆顶元素
DataType HeapTop(Heap* hp) {
assert(hp);
return hp->array[0];
}[10]获取堆的元素个数
堆的元素个数被size变量记录，因此直接返回size变量即可。
//获取堆中元素的个数
int HeapSize(Heap* hp) {
assert(hp);
return hp->size;
}[11]判断堆是否是空
当元素个数为0，堆自然是空的。
//判断堆是否是空
int HeapEmpty(Heap* hp) {
assert(hp);
return hp->size == 0;
}[12]删除整个堆
释放空间，指针置空，元素置0即可。
//销毁整个堆
void HeapDestroy(Heap* hp) {
assert(hp);
//只有指针不指向空才可以进行释放
if (hp->array) {
//释放堆上申请的空间
free(hp->array);
//将指针指向空，防止无意间被使用
hp->array = NULL;
hp->size = 0;
hp->capacity = 0;
}
}4.堆的整体实现代码
此代码是创建小堆，如果需要创建大堆，只需要在向上调整和向下调整函数中对比较大小的部分进行修改即可。
#define _CRT_SECURE_NO_WARNINGS
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//小堆
typedef int DataType;
typedef struct Heap {
//定义DataType类型的指针
//用来指向一段连续的数组空间
DataType* array;
//array指向的数组空间的容量
int capacity;
//array指向的数组空间内存储的元素个数
int size;
}Heap;
//堆的创建
void HeapCreate(Heap* hp, DataType _array[], int _size);
//堆中插入元素
void HeapPush(Heap* hp, DataType data);
//删除堆顶元素
void HeapPop(Heap* hp);
//返回堆顶元素的引用
DataType HeapTop(Heap* hp);
//获取堆中元素的个数
int HeapSize(Heap* hp);
//判断堆是否是空堆
int HeapEmpty(Heap* hp);
//销毁整个堆
void HeapDestroy(Heap* hp);
//堆的向下调整函数
void AdjustDown(Heap* hp, int parent);
//交换两个结点的元素
void Swap(DataType* left, DataType* right);
//检查堆的空间是否足够，不够会扩容
void HeapCheckCapacity(Heap* hp);
//堆的向上调整
void AdjustUp(Heap* hp, int child);
//交换堆中两个结点保存的值
void Swap(DataType* left, DataType* right) {
DataType temp = *left;
*left = *right;
*right = temp;
}
//堆的向下调整
//parent是双亲结点下标
//这里的child parent都是下标
void AdjustDown(Heap* hp, int parent) {
//标记左孩子的下标，因为可能只有左孩子没有右孩子
int child = parent * 2 + 1;
int size = hp->size;
//只要孩子结点的下标小于总结点的个数
//说明并没有越界
while (child < size) {
//找出两个孩子中最小的那个
//child+1<size 成立时说明右孩子结点存在
//hp->array[child + 1] < hp->array[child] 这个表达式成立说明右孩子比左孩子小
//那么child下标就要转移到右孩子
if (child + 1 < size && hp->array[child + 1] < hp->array[child])
child += 1;
//判断双亲结点是否比最小的孩子结点小
if (hp->array[child] < hp->array[parent]) {
Swap(&hp->array[parent], &hp->array[child]);
parent = child;
child = parent * 2 + 1;
}
else {
return;
}
}
}
//堆的向上调整
void AdjustUp(Heap* hp, int child) {
//parent是child结点的双亲结点的下标
int parent = (child - 1) / 2;
//循环是为了一直向上调整
//child下标不等于0说明还没有调整到根节点
while (child) {
//如果孩子结点的值小于双亲结点的值
//说明不满足小堆
if (hp->array[child] < hp->array[parent]) {
//交换孩子与双亲的值
//并且把孩子的下标和双亲的下标更新使得满足循环条件继续向上调整
Swap(&hp->array[parent], &hp->array[child]);
child = parent;
parent = (child - 1) / 2;
}
//满足小堆就可以退出了
else {
return;
}
}
}
//堆的创建
void HeapCreate(Heap* hp, DataType _array[], int _size) {
//assert检查指针hp是否存在
//当指针hp指向空，就会报错
assert(hp);
//根据传递的参数_size来为hp开辟指向的空间
//如果开辟失败，malloc函数会返回NULL，hp就会指向NULL
hp->array = (DataType*)malloc(_size * sizeof(DataType));
//判断空间是否开辟成功
if (hp->array == NULL) {
assert(0);
return;
}
//空间开辟成功，修改堆中的容量
hp->capacity = _size;
//空间开辟成功，开始存入元素
for (int i = 0; i < _size; i++) {
hp->array[i] = _array[i];
}
//修改堆中元素个数
hp->size = _size;
//开始从最后一个非叶子结点进行向下调整
//(hp->size - 2)/2 这是最后一个非叶子结点的下标
for (int i = (hp->size - 2) / 2; i >= 0; i--) {
AdjustDown(hp,i);
}
}
//检查堆中空间是否足够，不够要扩容
void HeapCheckCapacity(Heap* hp) {
assert(hp);
//当容量和元素个数相同说明空间满了
if (hp->capacity == hp->size) {
//newCapacity就是准备新申请的空间大小
int newCapacity = hp->capacity * 2;
//申请新空间
DataType* temp = (DataType*)malloc(sizeof(DataType) * newCapacity);
//判断空间是否成功申请
//申请失败的话malloc函数会返回NULL
if (temp == NULL) {
assert(0);
return;
}
//将原空间的元素复制到新空间
for (int i = 0; i < hp->size; i++) {
temp[i] = hp->array[i];
}
//释放原空间
free(hp->array);
//将指针指向新空间
hp->array = temp;
//更新容量
hp->capacity = newCapacity;
}
}
//给堆中插入元素
void HeapPush(Heap* hp, DataType data) {
//首先要检测容量
HeapCheckCapacity(hp);
hp->array[hp->size] = data;
hp->size++;
//这里就需要向上调整了，因为插入元素后可能会破坏堆的结构
AdjustUp(hp, hp->size - 1);
}
//删除堆顶元素
void HeapPop(Heap* hp) {
//判断hp指针是否指向空，指向空就不能进行删除操作
if (HeapEmpty(hp)) {
return;
}
//交换堆顶元素和最后一个结点的元素
Swap(&hp->array[0], &hp->array[hp->size-1]);
hp->size--;
//从堆顶进行向下调整
AdjustDown(hp,0);
}
//返回堆顶元素
DataType HeapTop(Heap* hp) {
assert(hp);
return hp->array[0];
}
//获取堆中元素的个数
int HeapSize(Heap* hp) {
assert(hp);
return hp->size;
}
//判断堆是否是空
int HeapEmpty(Heap* hp) {
assert(hp);
return hp->size == 0;
}
//销毁整个堆
void HeapDestroy(Heap* hp) {
assert(hp);
//只有指针不指向空才可以进行释放
if (hp->array) {
//释放堆上申请的空间
free(hp->array);
//将指针指向空，防止无意间被使用
hp->array = NULL;
hp->size = 0;
hp->capacity = 0;
}
}
int main() {
DataType arr[] = { 100,99,88,77,66,55,44,33,22,11,10,9,8,7,6,5,4,3,2,1};
Heap Hp;
HeapCreate(&Hp,arr,sizeof(arr)/sizeof(arr[0]));
//HeapPush(&Hp, 2);
//HeapPop(&Hp);
for (int i = 0; i < Hp.size; i++) {
printf("%d ", Hp.array[i]);
}
printf("n");
printf("%dn", HeapEmpty(&Hp));
printf("%dn", HeapTop(&Hp));
printf("%dn", HeapSize(&Hp));
}最后
以上就是不安茉莉为你收集整理的数据结构：堆1.堆的引入 (2)堆的概念2.堆的特殊情况3.堆的局部实现4.堆的整体实现代码的全部内容，希望文章能够帮你解决数据结构：堆1.堆的引入 (2)堆的概念2.堆的特殊情况3.堆的局部实现4.堆的整体实现代码所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复