数据结构详解：堆的实现与应用

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

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

堆的核心操作

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

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

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

（1）堆的数组结构

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

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

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

（2）堆的初始化操作

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

// 初始化
void Preliminary(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) {
        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;
    // 上浮调整
    Adjust(Newnode->data, Newnode->size);
}

● 堆的插入：上浮调整

我们将这个新插入孩子节点下标传过去，注意是传址操作！然后算他的父节点下标位置，在用 while 循环来一直进行判断是否需要调整这个孩子节点和它的父子节点，这里需要理解循环的条件，已经调整完之后需要进行的两个操作，请看下面的代码：

// 上浮调整
void Adjust(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 Disposal(Heap* Newnode) {
    // 断言空指针
    assert(Newnode);
    // 交换根节点与最后一个下标的孩子节点
    Exchange(&Newnode->data[0], &Newnode->data[Newnode->size]);
    Newnode->size--;
    // 下沉调整
    Underneath(Newnode->data, Newnode->size);
}

下面进行最后一步：循环比较此时的根节点和它的孩子节点，哪个大交换哪个，如果小于孩子节点，就结束循环，下面是代码参照。

// 下沉调整
void Underneath(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 Free(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("释放成功");
}

堆的常见运用

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

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

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

堆的完整代码与思维逻辑

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

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX 10

typedef struct Heap {
    int size;
    int MAX_size;
    int* data;
} Heap;

// 声明函数
void Preliminary(Heap* Newnode);
void Adjust(int* data, int child);
void Insert(Heap* Newnode, int data);
void Underneath(int* data, int size);
void Exchange(int* p1, int* p2);
void Disposal(Heap* Newnode);
void Printf_t(Heap Newnode);
void Free(Heap* Newnode);

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

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

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

// 上浮调整
void Adjust(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 Insert(Heap* Newnode, int data) {
    if (Newnode == NULL) {
        printf("空间无效\n");
        return;
    }
    if (Newnode->size == Newnode->MAX_size) {
        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;
    Adjust(Newnode->data, Newnode->size);
}

// 下沉调整
void Underneath(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;
        }
    }
}

// 删除
void Disposal(Heap* Newnode) {
    assert(Newnode);
    Exchange(&Newnode->data[0], &Newnode->data[Newnode->size]);
    Newnode->size--;
    Underneath(Newnode->data, Newnode->size);
}

// 打印
void Printf_t(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");
}

// 堆的释放
void Free(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("释放成功");
}