数据结构：堆的概念与 C 语言实现

一、堆是什么？

1. 堆的定义

堆： 堆是一种特殊的完全二叉树，在此基础上增加了一些有序性约束。

2. 堆的分类

堆从排序的角度，被分为两类：大堆和小堆。

• 大堆 在大堆中，任何一个父结点的值都要大于或等于子结点的值（只是父亲与孩子之间的比较，与兄弟结点无关）。

如图，这就是一个大堆：

• 小堆 而在小堆中恰恰相反，任何一个子结点的值都要大于或等于父结点的值（只是父亲与孩子之间的比较，与兄弟结点无关）。

如图，这就是一个小堆：

3. 堆的特点

由于在大堆中，任何一个父结点的值都要大于或等于子结点的值；在小堆中，任何一个子结点的值都要大于或等于父结点的值。故堆有一个很重要的特点：在堆中，根结点的值最大或最小，故可通过堆来找极大值和极小值。

二、堆的实现（小堆）

（本文实现的堆是小堆，但原理一样）

1. 用什么来实现？

之前，我们讲了完全二叉树的存储，提到完全二叉树的编号是连续的。对于完全二叉树来说，我们可以用数组来进行存储，用下标来进行编号。而堆，就是一个完全二叉树，所以直接使用数组实现即可。

综上所诉，使用数组的结构来实现堆更优。

2. 实现思路

与顺序表同理，堆的实现也应该有三名成员：

1. 指向一个数组的指针
2. 堆内的总元素
3. 堆内的总容量

3. 代码实现

本文以创建一个 int 类型的堆为例

（1）创建头文件&源文件

在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱。

• 创建了一个 Heap.h 头文件，用于存放函数的声明和一些库函数的头文件。
• 创建了一个 Heap.c 源文件，用于放函数的定义 (堆的主体)。
• 还有一个 Test.c 源文件，用于测试实现的堆的运行效果。

（2）定义堆（定义）

首先我们要定义一个堆。

代码演示：（内有注释） （在头文件 Heap.h 中写）

//重定义，方便修改类型
typedef int HPDataType;

//定义堆
typedef struct Heap {
    HPDataType* a; //数组指针
    int size;      //总元素
    int capacity;  //容量
} Heap;

在定义堆的代码中，有两个需要注意的点： 本文是以 int 类型为例，但如果以后要将堆的类型修改成 char 类型或是其他类型一个一个修改就很麻烦。所以我们重定义 int 类型为 HPDataType，并将接下来代码中的 int 类型全部写成 HPDataType。这是为了方便我们以后对类型进行修改，仅需将 int 改为其他类型即可。 在定义堆的同时重定义堆变量名为 Heap 方便以后使用。

（3）堆的初始化（初始化）

定义完堆后，肯定要对堆进行初始化，内容全部置 0 / NULL。

代码演示：（内有注释） （其中 hp 是一个堆指针类型的指针，下同）

在 Heap.h 头文件中写到：

// 堆的初始化
void HeapInit(Heap* hp);

在 Heap.c 源文件中写到：

// 堆的初始化
void HeapInit(Heap* hp) {
    assert(hp); //断言空指针
    hp->a = NULL;
    hp->capacity = 0;
    hp->size = 0; //全部初始化置 0 / NULL
}

在写堆的实现的代码中，有一个很重要的点： 当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的。故为了我们的代码更加健壮，可以加入 assert 断言 来判断是否符合条件，在之后的代码中也都有。

（4）堆的销毁（销毁）

在我们的程序运行完毕后，当然要对堆进行销毁，以免占用内存。

代码演示：（内有注释） （其中 hp 是一个堆指针类型的指针，下同）

在 Heap.h 头文件中写到：

// 堆的销毁
void HeapDestory(Heap* hp);

在 Heap.c 源文件中写到：

// 堆的销毁
void HeapDestory(Heap* hp) {
    assert(hp); //断言空指针
    free(hp->a); //释放内存
    hp->a = NULL;
    hp->capacity = 0;
    hp->size = 0; //全部初始化置 0 / NULL
}

（5）插入数据（入堆）

• 第一步：怎么插入？ 在入堆时，由于堆的本质是数组，故从头或中间插入很不方便，还要挪动数据，故我们选择尾插数据入堆。

• 第二步：空间不够时咋办？ 堆的空间是动态管理的，故当堆的空间不足时，可再开辟一些空间使用（动态增容）。但是存在一个问题：我们到底要开辟多大的空间来使用呢？

1. 若一次性开辟的空间过大，可能会造成空间的浪费。
2. 若一次性开辟的空间过小，就可能会导频繁的开辟空间，这样运行的效率就会大大降低。 经过科学研究，发现每次增容 2 倍 & 3 倍 空间最为合适。当原空间为 100 的空间不足时，就增容到 200 空间。（本文选择的是每次增容 2 倍）。

• 第三步：调整堆 在插入之后，该堆就不一定还是小堆了，故需要做出调整，将尾插的数据向上调整。

那么该怎么调整呢？ 由于我们建的是小堆，所以若孩子小于父亲，孩子就要向上调整，将父亲与孩子的值对调。直到父亲小于孩子，调整结束。

代码演示：（内有注释） （其中 hp 是一个堆指针类型的指针，下同）

在 Heap.h 头文件中写到：

// 堆的插入
void HeapPush(Heap* hp, HPDataType x);

在 Heap.c 源文件中写到：（插入函数）

// 堆的插入（尾插 + 调整）
void HeapPush(Heap* hp, HPDataType x) {
    assert(hp); //断言空指针
    if (hp->size == hp->capacity) //当 size=capacity 时就表示空间不足，此时需要增容，故进入 if 语句
    {
        //先设置新变量，增容后再赋值
        int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity; //设置一个三目操作符判断原空间是否为 0
        //当原空间为 0 时给空间开辟 4 字节；当原空间不为 0 时给空间增容 2 倍
        HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType)); //由于是在原空间的基础上给空间增容，故我们这里使用 realloc 函数 增容
        //增容大小为上面的 newcapacity *（类型大小）
        if (tmp == NULL) //加一个 if 语句 防止增容失败
        {
            perror("realloc fail");
            return;
        }
        //没有问题后就赋值
        hp->a = tmp;
        hp->capacity = newcapacity;
    }
    hp->a[hp->size] = x;
    hp->size++;
    AdjustUp(hp->a, hp->size - 1); //插入完后就向上调整
}

（向上调整函数）

// 将尾插的元素向上调整
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 {
            break;
        }
    }
}

（交换函数）

// 交换两个数的值
void Swap(HPDataType* x, HPDataType* y) {
    HPDataType tmp = *x;
    *x = *y;
    *y = tmp;
}

（6）删除数据（出堆）

对于堆来说，要删除数据一般都是删除堆顶的元素。但是删除后想要调整回一个小堆就不容易了。所以我们采用一种间接删除的方式。

方法：先将堆顶和堆尾的值交换，然后删除堆尾数据。此时相当于把之前的堆顶数据删除了。而且对于数组来说尾删是很简单的，只需要将总个数减一就行。然后就开始处理首元素了，和尾插同理，需要调整，但这里是向下调整。由于我们建的是小堆，所以若父亲大于孩子，父亲就要向下调整，将父亲与孩子的值对调。直到父亲小于孩子，调整结束。

代码演示：（内有注释） （其中 hp 是一个堆指针类型的指针，下同）

在 Heap.h 头文件中写到：

// 堆的删除
void HeapPop(Heap* hp);

在 Heap.c 源文件中写到：（删除函数）

// 堆的删除（交换 + 头删 + 调整）
void HeapPop(Heap* hp) {
    assert(hp);
    assert(hp->size > 0); //断言空指针
    //断言顺序表不能为空
    Swap(&(hp->a[0]), &(hp->a[hp->size - 1]));
    hp->size--; //先将头部和尾部的值交换
    //并且 size--（类似删除尾部）
    AdjustDown(hp->a, 0, hp->size); //将头部的数据向下调整
}

（向下调整函数）

// 将交换的元素向下调整
void AdjustDown(HPDataType* a, int parent, int size) {
    // 先假设左孩子小
    int child = 2 * parent + 1;
    while (child <= size - 1) {
        if (child + 1 <= size - 1 && a[child + 1] < a[child]) {
            child++;
        }
        if (a[child] < a[parent]) //若父亲大于孩子，父亲就要向下调整
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else {
            break;
        }
    }
}

（交换函数）

// 交换两个数的值
void Swap(HPDataType* x, HPDataType* y) {
    HPDataType tmp = *x;
    *x = *y;
    *y = tmp;
}

（7）获取堆顶元素

这个很简单，直接用下标进行访问数据，再返回所对应的值。

代码演示：（内有注释） （其中 hp 是一个堆指针类型的指针，下同）

在 Heap.h 头文件中写到：

// 取堆顶的数据
HPDataType HeapTop(Heap* hp);

在 Heap.c 源文件中写到：

// 取堆顶的数据
HPDataType HeapTop(Heap* hp) {
    assert(hp);
    assert(hp->size > 0); //断言空指针
    //断言顺序表不能为空
    return hp->a[0];
}

（8）获取堆的数据个数

这个很简单，直接返回所对应的值。

代码演示：（内有注释） （其中 hp 是一个堆指针类型的指针，下同）

在 Heap.h 头文件中写到：

// 堆的数据个数
int HeapSize(Heap* hp);

在 Heap.c 源文件中写到：

// 堆的数据个数
int HeapSize(Heap* hp) {
    assert(hp); //断言空指针
    return hp->size;
}

（9）检测堆是否为空

这个很简单，如果堆为空返回非零结果，如果不为空返回 0。

代码演示：（内有注释） （其中 hp 是一个堆指针类型的指针，下同）

在 Heap.h 头文件中写到：

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回 0
int HeapEmpty(Heap* hp);

在 Heap.c 源文件中写到：

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回 0
int HeapEmpty(Heap* hp) {
    assert(hp); //断言空指针
    return hp->size == 0;
}

三、完整代码实现

1. Heap.h

用于存放用来放函数的声明和一些库函数的头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//重定义，方便修改类型
typedef int HPDataType;

//定义堆
typedef struct Heap {
    HPDataType* a; //数组指针
    int size;      //总元素
    int capacity;  //容量
} Heap;

// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

2. Heap.c

用于用来放函数的定义 (堆的主体)

#include "Heap.h"

// 堆的初始化
void HeapInit(Heap* hp) {
    assert(hp); //断言空指针
    hp->a = NULL;
    hp->capacity = 0;
    hp->size = 0; //全部初始化置 0 / NULL
}

// 堆的销毁
void HeapDestory(Heap* hp) {
    assert(hp); //断言空指针
    free(hp->a); //释放内存
    hp->a = NULL;
    hp->capacity = 0;
    hp->size = 0; //全部初始化置 0 / NULL
}

// 交换两个数的值
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 {
            break;
        }
    }
}

// 堆的插入（尾插 + 调整）
void HeapPush(Heap* hp, HPDataType x) {
    assert(hp); //断言空指针
    if (hp->size == hp->capacity) //当 size=capacity 时就表示空间不足，此时需要增容，故进入 if 语句
    {
        //先设置新变量，增容后再赋值
        int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity; //设置一个三目操作符判断原空间是否为 0
        //当原空间为 0 时给空间开辟 4 字节；当原空间不为 0 时给空间增容 2 倍
        HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType)); //由于是在原空间的基础上给空间增容，故我们这里使用 realloc 函数 增容
        //增容大小为上面的 newcapacity *（类型大小）
        if (tmp == NULL) //加一个 if 语句 防止增容失败
        {
            perror("realloc fail");
            return;
        }
        //没有问题后就赋值
        hp->a = tmp;
        hp->capacity = newcapacity;
    }
    hp->a[hp->size] = x;
    hp->size++;
    AdjustUp(hp->a, hp->size - 1); //插入完后就向上调整
}

// 将交换的元素向下调整
void AdjustDown(HPDataType* a, int parent, int size) {
    // 先假设左孩子小
    int child = 2 * parent + 1;
    while (child <= size - 1) {
        if (child + 1 <= size - 1 && a[child + 1] < a[child]) {
            child++;
        }
        if (a[child] < a[parent]) //若父亲大于孩子，父亲就要向下调整
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else {
            break;
        }
    }
}

// 堆的删除（交换 + 头删 + 调整）
void HeapPop(Heap* hp) {
    assert(hp);
    assert(hp->size > 0); //断言空指针
    //断言顺序表不能为空
    Swap(&(hp->a[0]), &(hp->a[hp->size - 1]));
    hp->size--; //先将头部和尾部的值交换
    //并且 size--（类似删除尾部）
    AdjustDown(hp->a, 0, hp->size); //将头部的数据向下调整
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp) {
    assert(hp);
    assert(hp->size > 0); //断言空指针
    //断言顺序表不能为空
    return hp->a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp) {
    assert(hp); //断言空指针
    return hp->size;
}

// 堆的判空
int HeapEmpty(Heap* hp) {
    assert(hp); //断言空指针
    return hp->size == 0;
}

3. Test.c

用于测试实现的堆的运行效果

#include "Heap.h"

int main() {
    Heap H;
    HeapInit(&H);
    HeapPush(&H, 423);
    HeapPush(&H, 234);
    HeapPush(&H, 233);
    HeapPush(&H, 44);
    HeapPush(&H, 35);
    HeapPush(&H, 6235);
    while (!HeapEmpty(&H)) {
        printf("%d ", HeapTop(&H));
        HeapPop(&H);
    }
    printf("\n\n");
    HeapDestory(&H);
    return 0;
}