数据结构：堆的原理与 C 语言实现

数据结构：堆（Heap）

堆的概念

堆（Heap）是数据结构中一种特殊的计算机结构，是一种特殊的完全二叉树，为非线性的数据结构，一般用于优先队列、堆排序、Top-k 的问题等等。

完全二叉树是二叉树中的一种，它的节点满足以下规律，有且只有以下三种情况：

1. 有左右两个孩子
2. 只有左孩子
3. 没有孩子（叶子节点）

叶子节点只可能在最大的两层出现且在最左层的叶子节点都集中在左侧。如下图理解：

注意：除了最后一层，如果每个父节点的孩子节点都有两个，它属于满二叉树，注意区别！

堆的性质

结构特性

从上面我们可以观察到，除了一层外，其它层是满层的，最后一层居左对齐。

堆序性质

可以看到，它的节点关键字是有序的，因此我们又可以将堆分为两类：

可以观察到大顶堆中，它的根节点关键字是整个树中是最大的，而每个父节点的孩子节点都要小于它的父节点。在小顶堆中，整个树的根节点关键字最小，且每个父节点关键字小于孩子节点的关键字。除此之外，有一个要补充的点：除了根节点的关键字处于两个极端之外，父节点的关键字是可以等于它的孩子节点的。

**大顶堆：**父节点的值 >= 子节点的值（根节点在整个树中最大）

**小顶堆：**父节点的值 <= 子节点的值（根节点在整个树中最小）

堆的物理逻辑 & 思维逻辑

咱们知道，堆是一种完全二叉树，但是我们选择的是数组方式的存储，没有用链表。我们的堆元素是依次存储到数组里面的，比如根节点对应数组下标 0（或 1），根节点的左子节点对应数组的 1（或 2），根节点的右子节点对应数组的 2（或 3），依次类推满足：从上到下，从左到右。思维逻辑方便我们在查找问题，以及写各种操作时借助二叉树来直观的体现，如果我们在数组上操作进行思维操作，那么会很乱。

堆的节点对应关系

因为我们是数组实现，节点下标之间的索引存在固定的数学关系：

如果堆在数组中的下标是从 0 开始，那么满足： 假如父节点在数组的下标为 i，它的左孩子节点在数组的下标为 2 * i + 1，右节点数组下标为：2 * i + 2

如果堆在数组中的下标是从 1 开始，那么满足： 假如父节点在数组的下标为 i，它的左孩子节点在数组的下标为 2 * i，右节点数组下标为：2 * i + 1

假如子节点在数组的下标为 k，它的父节点在数组中的下标为 (k - 1) / 2

例如：

在左边的大顶堆中，根节点在数组中的下标为 1，那么它的左子节点在数组中的下标按照公式得出 21=2，右孩子节点的数组下标为 21+1=3，反过来，它的子节点的数组下标为 3，它的根节点（父节点）数组下标为 (3-1)/2=1。右边的小顶堆也是同理！

在右边的小顶堆中，根节点的数组下标从 0 开始，它的根节点（父节点）下标为 0，那么它的左子节点下标按照公式为 20+1=1，它的右子节点数组下标为 20+2=2，反过来它的左子节点数组下标为 1，那么它的父节点数组下标按照公式为 (1-1)/2=0，同理，大顶堆也是如此！

堆的核心操作

首先我们需要用数组的形式来模拟完全二叉树，来依次完成下面的操作，时间复杂度都是 logN：

• 初始化操作：初始化我们要开辟一定的空间，并返回这个指向这个空间的指针
• 插入：向整个树中添加一个元素
  • （1）上浮：进行调整新插入的元素路径
• 删除：不同的删除操作之后我们需要保证余下的元素满足堆的规则，因此需要下面两个操作：
  • （1）下沉：调整删除后的堆顶元素路径
• 堆的销毁：我们会进行动态开辟，因此养成良好习惯，及时释放开辟的空间

上浮与下沉的作用说的通俗一些就是每次进行插入与删除操作后，通过它们来调节堆的节点，使它们满足堆的性质。

（1）堆的数组结构

堆的数组结构，需要一个计算当前存储量的，还有一个指向动态数组空间指针，以及最大存储个数。

下面我以根节点下标为 0 的大顶堆存储来进行举例！

#define MAX 10
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct Heap {
    int size;       // 当前元素个数
    int MAX_size;   // 最大存储个数
    int* data;      // 动态存储空间
} Heap;

（2）堆的初始化操作

初始化我们需要只需要让结构体里面的指针指向一片空间就可以，成员进行一些初始化设置，注意我们在这里实现的堆下标是从 0 开始，所以 size 初始化为 -1。有的堆是从下标 1 开始，记得区分！

// 初始化
void Init(Heap* Newnode) {
    Newnode->data = (int*)malloc(sizeof(int) * MAX); // 空间有效性的判断
    if (Newnode->data == NULL) {
        printf("空间开辟无效\n");
        return;
    }
    // 初始化内容
    Newnode->size = -1;
    Newnode->MAX_size = MAX;
}

（3）堆的插入节点

在插入节点之前：我们应该判断空间是否支持插入，这里面涉及了判断 NULL 以及空间大小判断。

在插入节点之后：因为我们写的是大顶堆，因此需要对刚插入的成员根据情况是否进行调整位置。

按照大顶堆的规则，根节点的关键字应该是最大的，保证每个父节点都要比它的孩子节点大，同时为了以后方便维护我们需要另外写两个函数：上浮调整函数、交换函数。

// 插入
void Insert(Heap* Newnode, int data) {
    // 判断空间是否存在
    if (Newnode == NULL) {
        printf("空间无效\n");
        return;
    }
    // 判断是否是满空间
    if (Newnode->size == Newnode->MAX_size - 1) {
        int * pc = (int *)realloc(Newnode->data, sizeof(int) * Newnode->MAX_size * 2);
        if (pc == NULL) {
            printf("扩容失败\n");
            return;
        }
        // 改变当前最大存储量
        Newnode->MAX_size += Newnode->MAX_size;
        // 连接
        Newnode->data = pc;
        printf("扩容成功\n");
    }
    Newnode->size++;
    Newnode->data[Newnode->size] = data;
    // 上浮调整
    SiftUp(Newnode->data, Newnode->size);
}

// 上浮调整
void SiftUp(int* data, int child) {
    // 计算父节点的关键字
    int parent = (child - 1) / 2;
    // 判断是否需要交换
    while (child > 0) {
        if (data[child] > data[parent]) {
            // 满足条件就交换
            Exchange(&data[child], &data[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else break;
    }
}

// 交换
void Exchange(int* p1, int* p2) {
    int x = *p1;
    *p1 = *p2;
    *p2 = x;
}

（4）堆的删除节点

删除堆中的某个节点，咱们如果直接删除尾部的孩子节点，并没有什么意义，所以咱们来进行删头，也就是删除根节点，我们原先已经将堆按照大顶堆规则排列，那么我们如果删除头，取的是整个堆的最大元素，这非常适合排序！（时间复杂度是 logN）

● 堆的删除：下沉调整

那么重点来了：如果我们删除根节点，那么再去一个个摞另外的元素重新排列吗？不，这样效率很低。下面介绍一个方法：将根节点与最后一个孩子节点交换位置，然后元素个数 size 减一，接下来我们先说重新调整的一种方法：下沉。

上面是第一步：先交换两个元素，同时 size 减一。

// 删除
void Delete(Heap* Newnode) {
    // 断言空指针
    assert(Newnode);
    // 交换根节点与最后一个下标的孩子节点
    Exchange(&Newnode->data[0], &Newnode->data[Newnode->size]);
    Newnode->size--;
    // 下沉调整
    SiftDown(Newnode->data, Newnode->size);
}

// 下沉调整
void SiftDown(int* data, int size) {
    int parent = 0;
    int child = 2 * parent + 1;
    // 比较父节点（根节点）与它的最大的孩子节点
    while (child < size) {
        // 先避免越界，再比较两个孩子节点，找最大的
        if (child + 1 < size && data[child] < data[child + 1]) {
            ++child;
        }
        if (data[child] > data[parent]) {
            Exchange(&data[child], &data[parent]);
            // 改变父节点下标
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

（5）堆的释放

咱们可以先释放元素，再释放开辟好的空间，这里注意释放的指针必须是指向空间的起始位置！

// 堆的释放
void FreeHeap(Heap *Newnode) {
    assert(Newnode);
    int num = 0;
    while (num <= Newnode->size) {
        Newnode->data[num] = 0;
        num++;
    }
    // 释放指针
    int* Node = Newnode->data;
    free(Node);
    Node = NULL;
    printf("释放成功");
}

// 打印
void PrintHeap(Heap Newnode) {
    if (Newnode.size == 0) {
        printf("没有元素，无法打印\n");
        return;
    }
    int num = 0;
    printf("堆元素：");
    while (num <= Newnode.size) {
        printf("%d ", Newnode.data[num]);
        num++;
    }
    printf("\n");
}

堆的常见运用

1. 优先队列 这是一种特殊的数据结构，它的排列是顺序是按照元素的优先级的，注意不是插入的顺序。它可以在 O（1）的时间复杂度内获取当前优先级最高的元素，它的删除与插入与堆一样都是 logN。堆结构可以快速实现插入和删除操作，采用的数组又降低了难度。

2. Top K 问题 Top K 问题就是从一堆数据中找到前 K 个最大、最突出的元素，这点是不是很适合堆！？比如在一堆杂乱的元素中找到前 4 个最大的元素，这里刚好可以借助调整的上浮、下沉操作来实现。

3. 堆排序 核心思想就是利用父节点优先级高于子节点的特性，将无序数据排序成有序数据，这点直接用堆的调整函数就可以实现！

堆的完整代码 + 思维逻辑

首先咱们定义了一个结构体，这个结构体里面肯定有一个指向动态空间的指针，接下来肯定要涉及动态开辟已经初始化操作。随之就是给这个空间存储数据，这个过程也很简单，因为咱们得底层逻辑还是数组，只需要按照下标一个个存进去就可以。之后考虑到存进去的元素不符合大顶堆的规定，我们需要写一个调整函数，每次放入一个值需要与它的父节点比较，看是否交换位置，来实现初步的堆。最后是删除操作，咱们删除堆的堆顶，删除之后考虑到如果移动整个堆，那样就会很麻烦，因此我们使用特殊的删除方法：堆尾与堆头互换，然后删除堆尾，也就是下标减一。其次就是重新排序，我们只需要取整个堆的最大值放在堆头即可。以上就是整个思维逻辑！

int main() {
    int data = 0;
    Heap Newnode;
    // 初始化
    Init(&Newnode);
    // 插入
    for (int i = 10; i < 110; i += 10) {
        data = i;
        Insert(&Newnode, data);
    }
    // 删除
    Delete(&Newnode);
    // 打印
    PrintHeap(Newnode);
    // 堆的释放
    FreeHeap(&Newnode);
    return 0;
}