文章目录
- 前言
- 堆的概念及结构
- 堆初始化
- 堆的判空
- 堆的销毁
- 插入数据
- 删除数据
- 堆的数据个数
- 获取堆顶数据
- 用数组创建堆
- 对数组堆排序
- 有关topk问题
- 整体代码展示
- 写在最后
前言
🚩前面了解了树（-> 传送门 <-）的概念后，本章带大家来实现一个跟树有关的数据结构——堆（本章有对堆排序和
topk问题的讲解）。
🚩普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把 堆 (一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
如下图：
🚩所以，我们在实现 堆 的时候可以将它看作为一棵二叉树来思考，这是它的 逻辑结构 。但其 物理结构 是一个实实在在的 顺序数组 (在内存当中存储的形式)。
🚩那么接下来就开始实现一个属于自己的堆吧！
堆的概念及结构
-
本章是以大堆为例，只要会了大堆，小堆也是不在话下。
-
堆是把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并且它的任意元素 Ki(i = 0, 1, 2, 3, …, n - 1) 都满足 Ki <= K(i * 2 + 1) 且 Ki <= (i * 2 + 2) （ 或者 Ki >= K(i * 2 + 1) 且 Ki >= K(i * 2 + 2) ），这样的堆我们称之为 小堆（ 或者 大堆 ）。我们还可以将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
-
有了对堆的概念和性质的理解，相信大家对堆的元素是如何在数组中存储的（物理结构）明白了许多，就是依照上面大堆小堆的概念来维持存储关系的。
图示：
- 观察上图可知，第一张图是一个大堆的逻辑结构和物理结构，其每个结点的左右子结点都比这个结点要小或者等于；第二张图是一个小堆的逻辑结构和物理结构，其每个结点的左右子结点都比这个结点要大或者等于。所以，一个堆，他只能是小堆或者大堆，不具有这两个堆的性质的，都不属于堆，下面我们来判断一下那些是堆那些不是堆：
A. 100,60,70,50,32,65 // 这是一个大堆
B. 60,70,65,50,32,100 // 这不是堆
C. 65,100,70,32,50,60 // 这不是堆
D. 70,65,100,32,50,60 // 这不是堆
E. 32,50,80,70,65,100 // 这是一个小堆
F. 50,100,70,65,60,32 // 这不是堆
其实如果想要更好的判断，只需要将其逻辑结构画出来，就一目了然了。
了解了堆的概念和结构后，接下来就是实现啦！！！
堆初始化
- 首先我们需要三个文件：
heap.h，heap.c，test.c。heap.h用来存放所需头文件，堆的结构体和相关函数声明。heap.c用来实现相关函数接口，test.c用来测试。
下面是所需头文件：
#include <stdio.h>
// assert断言所需
#include <assert.h>
// 动态内存开辟函数所需
#include <stdlib.h>
// bool类型所需
#include <stdbool.h>
// 拷贝函数所需
#include <string.h>
- 我们知道，堆的底层存储结构是一个顺序的数组，因此这里需要跟前面我们实现的顺序表一样用动态内存空间。使用动态空间，就需要一个变量来统计容量，当然，为了后面一些函数功能的需求，还需要一个变量来统计堆的数据个数。因此，一个堆的结构定义如下：
// 堆的元素的数据类型
typedef int HPDataType;
typedef struct Heap
{
// 指向存储数据的连续的空间（数组）
HPDataType* a;
// 统计当前堆中数据的个数
int size;
// 统计当前空间的容量
int capacity;
}Heap;
- 一个堆所需的函数接口声明如下：
// 以大堆为例
// 堆初始化
void HeapInit(Heap* php);
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n);
// 插入数据
void HeapPush(Heap* php, HPDataType x);
// 删除数据
void HeapPop(Heap* php);
// 获取堆顶数据
HPDataType HeapTop(Heap* php);
// 获取堆数据个数
int HeapSize(Heap* php);
// 堆判空
bool HeapEmpty(Heap* php);
// 堆的销毁
void HeapDestroy(Heap* php);
// 交换
void swap(HPDataType* a, HPDataType* b);
// 向上调整
void adjustup(HPDataType* a, int child);
// 向下调整
void adjustdown(HPDataType* a, int size, int parent);
// 堆排序
void HeapSort(HPDataType* a, int n);
// topk问题
void PrintTopK(HPDataType* a, int n, int k);
- 有了以上的铺垫，堆的初始化就是将堆的结构里的指针置为空，统计数据个数和统计空间容量的变量置为
0即可。(当然也可以初始化的时候就开个初始空间)
相关函数接口功能的实现：
// 堆初始化
void HeapInit(Heap* php)
{
// 防止传递一个NULL上来，传NULL的话php就是NULL，后面的操作就不能进行了
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
堆的判空
- 有了统计堆的数据个数的变量
size，判空就简单多了。只需要判断一下size是否为0即可，如果size为0，说明为空，返回true，如果size不为0，说明堆中有数据，返回false。
相关函数接口功能的实现：
// 堆判空
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}
堆的销毁
- 堆的销毁也很简单，将堆空间释放即可。当然
size跟统计容量的capacity也置为0。
相关函数接口功能的实现：
// 堆的销毁
void HeapDestroy(Heap* php)
{
assert(php);
free(php->a);
php->capacity = php->size = 0;
}
插入数据
-
首先，插入数据要看看容量够不够，如果不够，就需要扩容。
-
插入数据就是在数组的最后一个位置插入，由于
size是数据的个数也就是数组的长度，所以size就是指向堆的最后一个数据的下一个位置，因此我们只需要在size位置插入即可。当然，插入过后，多了一个数据，因此size要自加1。 -
当我们插入数据之后，现在堆的结构很可能就不是一个堆（以大堆为例）了，因此，这里需要对插入进来的那个数据执行一个向上调整的算法，图示：
- 对于向上调整算法，我们需要找到这个结点（假设下标为
child）的父亲结点（假设下标为parent），具体操作为：parent = (child - 1) / 2 ，找到父结点后，就与他进行比较，由于我们以大堆为例，所以如果child位置上的数据大于parent位置上的数据，就需要将这两个数据交换一下，然后循环往复，继续寻找父结点进行比较，直到到达应该处在的位置为止（直到是个堆为止）。
相关函数接口功能的实现：
// 插入数据
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
// 如果容量满了就扩容
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
// 在size位置插入数据，然后size自加1
php->a[php->size++] = x;
// 对插入的那个数据执行向上调整算法，重整堆
// php->size - 1是插入的那个数据的下标
adjustup(php->a, php->size - 1);
}
向上调整算法：
// 向上调整
void adjustup(HPDataType* a, int child)
{
// 找父结点
int parent = (child - 1) / 2;
while (child > 0)
{
// 如果child位置的数据大小大于parent位置的数据大小就交换
if (a[child] > a[parent])
{
// 交换
swap(&a[child], &a[parent]);
// 交换过后，child依旧指向开始指向的那个数据
child = parent;
// 继续找父结点
parent = (child - 1) / 2;
}
else break; // 如果小于等于了，说明此时的堆是个真正的堆了，直接跳出循环
}
}
这里有个swap函数，其实现为：
// 交换
// 注意是传递地址交换，因为形参的改变不改变实参
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
删除数据
-
删除数据其实是删除堆顶的数据，由于堆是由一个数组来存放数据的，那么我们该如何删除堆顶（数组的第一个元素数据）的数据呢？
-
这里我们将堆顶数据和数组的最后一个数据交换一下，然后
size减一，就实现了删除。 -
当然，删除过后，此时的堆已经不再是堆了，所以我们需要对新的堆顶数据执行一下向下调整算法，图示：
-
对于向下调整算法，我们先要找到该结点（假设下标为
parent）的孩子结点，而孩子结点又分为左孩子结点（下标为parent * 2 + 1）和右孩子结点（下标为parent * 2 + 2），所以我们需要找出两个孩子结点当中较大的那个，如果该节点的数据比较大的那个孩子结点的数据要小，那就进行交换，然后循环往复继续向下寻找孩子结点重整堆。 -
整个操作，我们可以先比较两个孩子的大小找出大的那个，然后在与大的这个孩子结点进行比较，如果父结点比他小（以大堆为例），说明这个孩子结点该上位了。然后继续向下执行这个操作。
相关函数接口功能的实现：
// 删除数据，删除堆顶的数据
void HeapPop(Heap* php)
{
// 判断php的合法性并且要保证堆不为空，空就不能删了
assert(php && !HeapEmpty(php));
// 将堆的第一个数据与堆的最后一个数据交换
swap(&php->a[0], &php->a[php->size - 1]);
// size减一表示删除最后一个数据
php->size--;
// 对新的堆顶执行向下调整算法
adjustdown(php->a, php->size, 0);
}
向下调整算法：
// 向下调整
void adjustdown(HPDataType* a, int size, int parent)
{
// 先假设大的那个孩子结点为左孩子结点
int child = parent * 2 + 1;
while (child < size) // 如果child小于此时数组的长度就继续
{
// 第一个判断是防止没有右孩子结点的情况
// 第二个判断是如果右孩子存在并且右孩子结点的数据大于左孩子结点的数据，就child加一指向右孩子结点
if (child + 1 < size && a[child + 1] > a[child]) child++;
// 如果父节点数据小于child结点数据，就交换重整堆
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else break; // 如果父节点数据大于child结点数据，说明堆已经调整完毕，直接跳出循环不在调整
}
}
堆的数据个数
- 由于我们定义了一个变量来统计堆的数据个数，所以在这里只需要返回那个变量的值即可。
相关函数接口功能的实现：
// 获取堆数据个数
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
获取堆顶数据
-
获取堆顶数据就是数组的第一个元素。
-
如果此时堆为空，就不能获取了。
相关函数接口功能的实现：
// 获取堆顶数据
HPDataType HeapTop(Heap* php)
{
assert(php && !HeapEmpty(php));
return php->a[0];
}
用数组创建堆
-
用数组创建堆就是将一个数组里面的所有元素拷贝到堆的数组里，然后进行建堆。
-
我们首先开辟一个堆空间（就是一段连续的数组），长度与给的数组的长度相同，然后将给的数组里的元素拷贝过来，最后将堆里面的数据进行建堆。
-
如何建堆？我们从最后一个结点的父节点开始，依次执行向下调整算法，直到根节点执行完全后，便建成了堆。当然我们也可以从第二个结点开始，依次执行向上调整算法，直到最后一个结点执行完后便建成了堆，不过这样的时间复杂度为
O(n * logn)，而前面的向下调整算法的方式的时间复杂度为O(n)，所以这里我们采用向下调整算法的方式来建堆。至于这两个调整算法的时间复杂度是如何计算出来的，这里就不做讨论，它的本质其实是有关数列求和的计算。
向下调整算法方式建堆图示：
- 有了上面的思路，接下来就是代码实现了。
相关函数接口功能的实现：
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n)
{
// php不能为NULL，a不能为NULL
assert(php && a);
// 开辟可存放n个数据的堆空间
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
// 拷贝数据
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = php->capacity = n;
// 从最后一个结点的父节点开始依次执行向下调整算法，直到根结点执行完后结束
// 这里i为什么初始化 (n - 2) / 2 呢？ 其实就是最后一个结点的父节点的下标
// 前面说了，寻找父节点的下标是 (child - 1) / 2
// 这里是寻找最后一个结点的父结点，而最后一个结点的下标是 (n - 1)（n是数组长度）
// 所以它的父节点就是 (n - 1 - 1) / 2 , 也就是(n - 2) / 2
for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(php->a, n, i);
}
对数组堆排序
-
有了建堆的认识，堆排序也不难，只不过需要注意几个细节。
-
对数组排序，首先就是要对这个数组建堆，如果是要将数组升序，就建为大堆，如果是要将数组降序，就建为小堆，为什么呢？这里以升序为例进行讲解，弄懂了升序，降序也只是大于小于号的问题了。
-
当数组建成大堆形式后（同样的，使用向下调整算法建堆），堆顶元素是最大的，此时我们可以将堆顶元素与最后一个元素进行交换，这样最大的元素就到了数组的末尾了。然后我们对这个处在数组最后一个位置的最大元素视而不见，将交换过去的堆顶元素执行向下调整算法，这时，第二大的元素就到了堆顶，然后此时的堆顶元素继续与最后一个元素进行交换 （注意第一个交换过去的最大的元素已经不在范围内了，也就是说每将一个当前最大的数交换过去后，可视作
size减一一次） ，然后再将交换过去的堆顶元素执行向下调整算法…这样循环往复，最终该数组就变成了升序。
相关函数接口功能的实现：
// 堆排序
void HeapSort(HPDataType* a, int n)
{
assert(a);
// 向下调整, 这里是建大堆
for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(a, n, i);
// 排序（建的大堆就是升序）
int k = n - 1;
while (k > 0)
{
swap(&a[0], &a[k]);
adjustdown(a, k, 0);
k--;
}
}
有关topk问题
-
如何在百万个成绩数据里面找出前十个最好的？这就是典型的
topk问题。可以看到，它需要处理的数据非常多（当然也有的很少，不过面试一般就是问多的情况，让你找出前k个最那啥的），因此这里需要用到堆来解决。 -
为什么堆可以解决呢？堆的堆顶要么是整个堆里最大的元素，要么是整个堆里最小的元素。根据这一性质，假如求很多数据中前
k个最小的数据，我们可以先开辟一个堆空间，该堆空间可以存放k个数据，然后我们将很多数据中的前k个数据拷贝进堆里，并将其建成大堆，此时堆的堆顶元素就是堆里所有元素最大的那一个，接着，我们从很多数据的第k个数开始，遍历这些数据，如果该数据小于此时堆顶的数据，就将堆顶数据更新为这个小的数据，然后对其执行向下调整算法，执行完过后，堆顶还是堆中最大的那个元素，就这样判断并操作，直到遍历结束，堆中就是那前k个最小的数啦。最后将这些数打印即可。（找前k个最小的数就是建大堆，反之，建小堆，这里就不作讨论了） -
原理（以求前
k个最小的数为例）：每次比堆顶小的元素入堆并调整后，之前堆中最大的元素被抛弃，新的最大的元素上位了，这样循环往复下去，每次操作除大的进小的，当然最后堆中就是前k个最小的数啦。
相关函数接口功能的实现：
// topk问题
void PrintTopK(HPDataType* a, int n, int k)
{
assert(a);
// 开辟能够存放k个数据的堆空间
HPDataType* topk = (HPDataType*)malloc(sizeof(HPDataType) * k);
if (topk == NULL)
{
perror("malloc fail");
exit(-1);
}
// 拷贝前k个数据进堆
memcpy(topk, a, sizeof(HPDataType) * k);
// 找前k个最小的，建大堆
for (int i = (k - 2) / 2; i >= 0; i--) adjustdown(topk, k, i);
// 对topk堆进行 除大的进小的 操作
for (int i = k; i < n; i++)
{
if (a[i] < topk[0])
{
topk[0] = a[i];
// 每次进来一个较小的元素都要执行一遍向下调整算法来调整堆
adjustdown(topk, k, 0);
}
}
// 打印 topk
for (int i = 0; i < k; i++) printf("%d ", topk[i]);
// 最后使用完堆后记得释放
free(topk);
}
整体代码展示
heap.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
// 以大堆为例
// 堆初始化
void HeapInit(Heap* php);
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n);
// 插入数据
void HeapPush(Heap* php, HPDataType x);
// 删除数据
void HeapPop(Heap* php);
// 获取堆顶数据
HPDataType HeapTop(Heap* php);
// 获取堆数据个数
int HeapSize(Heap* php);
// 堆判空
bool HeapEmpty(Heap* php);
// 堆的销毁
void HeapDestroy(Heap* php);
// 交换
void swap(HPDataType* a, HPDataType* b);
// 向上调整
void adjustup(HPDataType* a, int child);
// 向下调整
void adjustdown(HPDataType* a, int size, int parent);
// 堆排序
void HeapSort(HPDataType* a, int n);
// topk问题
void PrintTopK(HPDataType* a, int n, int k);
heap.c
#include "heap.h"
// 堆初始化
void HeapInit(Heap* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
// 数组创建堆
void HeapCreateArray(Heap* php, HPDataType* a, int n)
{
assert(php && a);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = php->capacity = n;
for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(php->a, n, i);
}
// 插入数据
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size++] = x;
adjustup(php->a, php->size - 1);
}
// 删除数据，删除堆顶的数据
void HeapPop(Heap* php)
{
assert(php && !HeapEmpty(php));
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
adjustdown(php->a, php->size, 0);
}
// 获取堆顶数据
HPDataType HeapTop(Heap* php)
{
assert(php && !HeapEmpty(php));
return php->a[0];
}
// 获取堆数据个数
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}
// 堆判空
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}
// 堆的销毁
void HeapDestroy(Heap* php)
{
assert(php);
free(php->a);
php->capacity = php->size = 0;
}
// 交换
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = 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 adjustdown(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child + 1] > a[child]) child++;
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}
// 堆排序
void HeapSort(HPDataType* a, int n)
{
assert(a);
// 向下调整, 这里是建大堆
for (int i = (n - 2) / 2; i >= 0; i--) adjustdown(a, n, i);
// 排序（建的大堆就是升序）
int k = n - 1;
while (k > 0)
{
swap(&a[0], &a[k]);
adjustdown(a, k, 0);
k--;
}
}
// topk问题
void PrintTopK(HPDataType* a, int n, int k)
{
assert(a);
HPDataType* topk = (HPDataType*)malloc(sizeof(HPDataType) * k);
if (topk == NULL)
{
perror("malloc fail");
exit(-1);
}
memcpy(topk, a, sizeof(HPDataType) * k);
// 找前k个最小的，建大堆
for (int i = (k - 2) / 2; i >= 0; i--) adjustdown(topk, k, i);
for (int i = k; i < n; i++)
{
if (a[i] < topk[0])
{
topk[0] = a[i];
adjustdown(topk, k, 0);
}
}
for (int i = 0; i < k; i++) printf("%d ", topk[i]);
free(topk);
}
test.c
#include "heap.h"
void test1()
{
Heap hp;
HeapInit(&hp);
HeapPush(&hp, 22);
HeapPush(&hp, 122);
HeapPush(&hp, 16);
HeapPush(&hp, 45);
HeapPush(&hp, 56);
HeapPush(&hp, 18);
HeapPush(&hp, 134);
HeapPush(&hp, 99);
HeapDestroy(&hp);
}
void test2()
{
Heap hp;
HeapInit(&hp);
int arr[] = { 34,113,78,44,98,99,35,26,18,68 };
int n = sizeof(arr) / sizeof(arr[0]);
HeapCreateArray(&hp, arr, n);
while (!HeapEmpty(&hp))
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
printf("\n");
HeapDestroy(&hp);
}
void test3()
{
int arr[] = { 34,113,78,44,98,99,35,26,18,68 };
int n = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, n);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
void testTopK()
{
int arr[] = { 34,113,78,44,98,99,35,26,18,68 };
int n = sizeof(arr) / sizeof(arr[0]);
PrintTopK(arr, n, 5);
}
int main()
{
//test1();
test2();
test3();
testTopK();
return 0;
}
写在最后
💝
❤️🔥后续将会持续输出有关数据结构与算法的文章，你们的支持就是我写作的最大动力！
感谢阅读本小白的博客，错误的地方请严厉指出噢~
