数据结构堆 & 优先队列的概念、实现及应用场景

名称：Doubletful的博客

💠数据结构专栏

签名：路漫漫其修远兮，吾将上下而求索

文章目录

• • 前言
• 一、概念
• • 1.二叉树概念
  • 2.堆的概念
  • 3.堆的数组表示
  • 4.为何必须是完全二叉树
• 二、代码实现
• • 1.准备
  • 2.头文件内容总览
  • 3.初始化堆
  • 4.判断空间容量
  • 5.添加数据
  • 6.向上调整算法
  • 7.删除数据
  • 8.向下调整算法
  • 9.获取堆顶元素
  • 10.判断是否为空
  • 11.销毁堆
• 三、应用场景
• • 1.堆排序
  • • 1.1.建堆
    • • 1.1.1.大小堆选择
      • 1.1.2.向上调整建堆
      • 1.1.3.向下调整建堆
      • 1.1.4.方法二时间复杂度分析
    • 1.2.排序循环
  • 2.TopK问题
  • • 2.1.结论二代价解释
    • 2.2.经典解法介绍
    • 2.3.大小堆选择
    • 2.4.创建带有十万个随机数的文件
    • 2.5.在电脑中找到数据文件
    • 2.6.TopK代码实现
  • 3.其他应用场景简介
• 四、总结
• • 1.一份测试代码
  • 2.整体总结

前言

——在计算机科学中，堆（Heap）是一种极其基础而又强大的数据结构，本文将从二叉树的基础出发，逐步深入堆的核心概念，剖析其实现细节，并探讨其在实际工程中的典型应用。 文章将使用C语言实现基础数据结构——堆，主要内容包括： 1.使用头文件声明、源文件定义的形式实现 2.从二叉树到堆的概念，实现原理与操作接口的详解 3.提供完整的代码示例、图例和实际应用场景分析

一、概念

1.二叉树概念

堆本质上是一种特殊的完全二叉树。因此，在理解堆之前，我们需要先回顾二叉树的一些基本性质：

• 二叉树：每个节点最多有两个子节点的树结构。
• 满二叉树：二叉树的每一层的节点数都达到最大值，则称其为满二叉树。
• 完全二叉树：前 h – 1 层的节点数都达到最大值，最后一层不满，但从左到右必须是连续的。

堆要求其底层结构必须是一棵完全二叉树，这一限制使得堆可以用数组高效存储，而无需使用指针。 如果对“要求其底层结构必须是一棵完全二叉树”抱有疑问，请移至下文阅读。

2.堆的概念

堆是一种满足以下两种性质之一的完全二叉树： 👾大根堆（Max Heap）：每个节点的值都严格大于或等于其子节点的值。根节点是全局最大值。 👾小根堆（Min Heap）：每个节点的值都严格小于或等于其子节点的值。根节点是全局最小值。 注意：堆只规定了父节点与子节点的关系，但不规定左右子节点之间的大小关系，换言之，堆限制上下而不在意左右大小关系。 那么，我们应该用什么内置结构来从逻辑上实现堆呢？ 💡数组，并且使用结构体封装其属性元素个数与容量，与顺序表的物理结构一致，因此实现更注重于逻辑层面。

3.堆的数组表示

在数组中，使用下标位表示父节点与子节点的关系，具体性质如下： 🔹父亲的下标为 i 时，左孩子的下标为 2 * i + 1，右孩子的下标为 2 * i + 2， 左孩子在数组中的下标都为奇数，右孩子在数组中的下标都为偶数。 🔸当任意孩子在数组中的下标为 j 时，其父亲在数组中的下标为 (j – 1) / 2，无论是左孩子或右孩子都通用，因为计算向下取整（整型性质）。 解释：通过右孩子找到其父节点的计算为 (2 * i + 2) – 1 等于 (2 * i + 1) / 2 等于 i + 0.5 后向下取整等于 i，找到对应父节点下标。

数据结构堆的物理结构与逻辑结构示例图：

4.为何必须是完全二叉树

当二叉树出现比较极端的情况时，使用数组存储会很浪费空间： ☄️在实际应用场景下，这种情况不仅会非常常见，并且数据量级也将巨额增长，所以非满二叉树或完全二叉树并不适合使用数组存储。

二、代码实现

1.准备

前置知识：

• assert()函数介绍 C语言标准库中的调试宏，用于在程序运行时检查条件是否成立。若条件为假（0），则输出错误信息（文件、行号、表达式）并调用 abort() 终止程序，若条件为真（非0），则无动作。常用于捕捉“不可能发生”的逻辑错误、验证函数前置条件等。
• perror()函数介绍 C语言标准库函数，用于打印错误信息。调用格式：perror(“前缀字符串”)，输出格式为“前缀字符串：错误原因\\n”，常用于系统调用或库函数失败后，快速定位错误原因。
• exit()函数介绍 C语言标准库函数，用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统（0 or EXIT_SUCCESS 表示成功，-1 or EXIT_FAILURE 表示失败）。
• 布尔值 C语言并不自带布尔值作为内置数据类型，使用需引入标准库<stdbool.h>
• 交换函数 C语言并不自带交换函数，需手动实现，其中的数据类型 HPDataType 为手动定义的堆存储数据类型。

void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

2.头文件内容总览

注：代码部分如果直接复制不能成功运行，请将所有中文前的#替换为//

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h> #TopK问题生成随机数据需要
typedef int HPDataType;

typedef struct Heap
{
HPDataType* arr; #存储堆节点的数组
int size;
int capacity;
}HP;

#初始化堆
void HPInit(HP* php);

#添加数据
void HPPush(HP* php, HPDataType x);

#删除数据
void HPPop(HP* php);

#获取堆顶元素
HPDataType HPTop(HP* php);

#判断是否为空
bool HPEmpty(HP* php);

#销毁堆
void HPDestroy(HP* php);

初始化与销毁，返回堆顶元素和判空，添加与删除数据，看起来与之前的数据结构实现并无不同，但其中有两个隐藏的核心辅助函数，向上调整元素（上浮）与向下调整元素（下沉），分别在添加与删除处讲解。 注：实现部分皆使用小根堆演示，大根堆只需修改部分代码的判断条件即可。

3.初始化堆

void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}

传入堆，并断言传入的指针不为 NULL。 初始化作为堆载体的数组，并将属性容量和大小置零。

4.判断空间容量

void HPCheckCapacity(HP* php)
{
if (php->size == php->capacity)
{
int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
}

当第一次扩容时初始化容量为4，否则扩容为当前容量的二倍，扩容后需判断是否扩容成功，失败返回提示信息后退出程序，成功时再执行更新操作。

5.添加数据

void HPPush(HP* php, HPDataType x)
{
assert(php);
HPCheckCapacity(php);
#添加
php->arr[php->size++] = x;
#向上调整插入数据
ADJustUp(php->arr, php->size – 1);
}

传入堆，并断言传入的指针不为 NULL。 我们选择在堆尾插入数据时，会产生一个问题： 新插入的数据可能违反堆的规则（大根堆情况下比父节点大或小根堆情况下比父节点小），此时需要不断与其对应父节点交换，直到恢复堆序。 核心辅助函数向上调整算法 ADJustUp 负责添加时的交换，下面详细介绍。

6.向上调整算法

void ADJustUp(HPDataType* arr, int child)
{
#孩子对应的父亲下标
int parent = (child – 1) / 2;
#父亲比孩子大时交换(小堆情况)
while (arr[parent] > arr[child])
{
Swap(&arr[parent], &arr[child]);
#依次比较祖先父亲与孩子的关系
child = parent;
parent = (child – 1) / 2;
}
}

向上调整函数的参数为表示堆的数组及新插入数据的下标。 首先计算新插入数据(以下简称 x)的父节点下标，其次通过判断确定是否符合堆的规则，不符合就交换，并继续计算交换位置后的 x 对应的父节点下标，直到符合堆的规则为止。 注：当 child 等于 0 时，减 1 除 2 的计算结果为 -0.5，根据整型性质得出对应的 parent 也为 0，必然因为 arr[parent] 不大于 arr[child] 自然终止，因此不会越界访问，最多将 x 调整到根节点终止。

7.删除数据

void HPPop(HP* php)
{
assert(php && php->size);
#删除
#交换堆顶与堆底的数据
Swap(php->arr, &php->arr[php->size – 1]);
php->size—; #删除当前堆底数据
#向下调整数据
ADJustDown(php->arr, php->size, 0);
}

传入堆，断言传入指针不为 NULL 且堆中元素个数不为0。 删除堆底数据无实际意义，因此改为每次删除堆顶的值，方式为将堆顶的值与堆底的值交换，删除当前堆底的值（即原根结点的值），此时堆顶可能违反堆序，仍需不断与较大的子节点或较小的子节点交换，直到恢复堆序。 核心辅助函数向下调整算法 ADJustDown 负责删除时的交换，下面详细介绍。

8.向下调整算法

void ADJustDown(HPDataType* arr, int n, int parent)
{
#假设左孩子比右孩子小
int child = parent * 2 + 1;
#最多交换到叶节点防止越界访问(小堆情况)
while (child < n)
{
#右孩子比左孩子小，判断右孩子是否存在防止越界访问
if (child + 1 < n && arr[child + 1] < arr[child])
child++;
#孩子比父亲小时交换
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
#依次比较子孙父亲与孩子的关系
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

向下调整函数的参数为表示堆的数组，数组大小及堆顶下标。 由于是向下调整，需明确堆底的边界防止越界，因此传入数组大小。先计算出左孩子的下标位，并在循环中取左右孩子的较小值用于交换，此处需注意保证右孩子存在，即 child + 1 < n。 ✨为什么取左右孩子的较小值？ 在小堆情况时，设左孩子比右孩子大且父节点的值大于左孩子，需交换，那么在将父节点与左孩子交换后，新父节点的值依然不符合堆规，比右孩子大，所以需取左右孩子的较小值，使其在交换后完全符合堆的规则。 凭此我们找到了正确的交换子节点，之后的操作与向上调整算法大致相同，都是先判断，再交换，最后继续计算交换位置后对应的子节点下标，直到子节点比父节点大时或遍历到最后的叶节点时终止。

9.获取堆顶元素

HPDataType HPTop(HP* php)
{
assert(php && php->size);
return php->arr[0];
}

传入堆，断言传入指针不为 NULL 且堆中元素个数不为0。 直接根据下标返回堆顶元素即可。

10.判断是否为空

bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}

传入堆，并断言传入的指针不为 NULL。 数组下标的一个性质：各自下标位等同于其位置前的元素个数——因此通过 size 当前指向的下标位判断堆是否为空，为空返回 true，否则返回 false。

11.销毁堆

void HPDestroy(HP* php)
{
assert(php);
free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}

传入堆，并断言传入的指针不为 NULL。 释放开辟的动态空间并将指针初始化，初始化大小和容量。

三、应用场景

堆的设计初衷是为了高效获取极值，因此它的应用几乎都围绕这一特性展开。

1.堆排序

堆排序是堆结构最经典的应用之一，它充分利用了“堆顶必为极值”这一特性，实现了一种原地且最坏情况下时间复杂度为 O(N*logN) 的排序算法。 优点：空间复杂度为O(1)，最坏情况表现稳定，不存在退化到 O(N²) 的风险。 提问：为什么空间复杂度为O(1)，难道不需要创建数据结构堆吗？ 答：确实不需要，因为数据结构堆本身就是用数组实现的，并且被排序数组不遵循堆规问题也有解决办法，使用核心辅助函数即可将被排序数组"堆化"。

1.1.建堆

1.1.1.大小堆选择

首先需要明确一个易混淆的点： 若想得到升序序列，应使用大根堆，若想得到降序序列，应使用小根堆。 ⚙️为什么？ 堆排序的核心操作是：将堆顶元素与堆末尾元素交换，然后将末尾“切除固定”，再对新的堆顶向下调整恢复堆序。使用大根堆时，每次被切除并放到数组末尾的都是当前最大值，因此数组从后往前依次被填满最大值，最终整体呈升序。降序同理，每次被固定到数组末尾的都是当前最小值。

1.1.2.向上调整建堆

#方法一：向上调整建堆，时间复杂度为O(N*logN)
for (int i = 1; i < size; i++)
{
AdjustUp(arr, i);
}

i 从 1 开始调整，这意味着首先将 0 ~ 1 位调整为一个堆，在此基础上逐渐拓展调整范围，如同添加数据一样，先将新值插入在堆末尾，再使用向上调整算法使其符合堆规，此种做法的时间复杂度为O(N*logN)。 接下来重点介绍时间复杂度更优的方法二，并且详解时间复杂度的数学推导。

1.1.3.向下调整建堆

#方法二：向下调整建堆，时间复杂度为O(N)
for (int i = (size – 2) / 2; i >= 0; i—)
{
ADJustDown(arr, size, i);
}

i 从最后一个节点的父亲开始调整，最后一个节点下标为 size – 1，这意味着开始向下调整的位置是最后一个叶结点的父节点，即最后一个父节点。从该节点开始建堆，随着 i 每次向前递减，相当于每次在堆顶插入一个新值后，将新值向下调整，直到符合堆规。

1.1.4.方法二时间复杂度分析

🔹从上至下看，第一层有 2⁰ 个节点，最坏向下调整 h – 1 次，第二层有 2¹ 个节点，最坏向下调整 h – 2 次。 🔸从下至上看，第 h – 1 层有 2^h-2个节点，最坏向下调整 1 次，第 h – 2 层有 2^h-3个节点，最坏向下调整 2 次。 由此可以得到式子并计算，首先利用错位相减法化简等差乘等比的数列，其次利用等差数列求和公式化简并将结果转换为以 N 表示的形式，最后将得到的具体时间复杂度去除影响不大的项，得到O(N)。

1.2.排序循环

#将数组排为降序，时间复杂度为O(N*logN)
int end = size – 1;
#每次将当前最小值交换到数组末尾
while (end > 0)
{
Swap(arr, &arr[end]);
#将被交换到根节点的值向下调整到合适位置(使数组仍是小堆)
ADJustDown(arr, end, 0);
end—;
}

在建好小根堆后，依次将当前根节点的极值交换到数组末尾，end 负责控制交换的位置，以便从后向前遍历数组和固定交换到数组末尾的极值，终止条件为 end 位置无需进行交换操作时，也就是当 end 遍历到根节点时。

2.TopK问题

⇒一句话解释TopK问题：N 个数找最大或最小的前 K 个。 这里的 K 通常远远小于 N，例如从 1 亿条用户记录中找出积分最高的 10 名用户，因此依现实情况得出： 结论一：因堆顶必为极值的特性，它天然适合解此类问题。 结论二：我们不可能为了找 10 个数据而开辟一个 1 亿数据量的数组并排序（数据集在硬盘中存储，需转入运行时内存）。

2.1.结论二代价解释

所占内存过大，用存储整型的情况计算，共 4 × 10⁹ 个字节，所占内存约为 0.09GB，看起来好像还能接受，但如果存储的数据类型是双精度浮点数并且数据量级为 10 亿，所占内存约为 1.8GB。绝大多数的应用程序所占内存共 20~30GB，从总量对比来看，很明显这一极小的功能并不配占有着如此高的内存占比，此方法代价过大。 因此，这里只推荐一种简单又高效的方法解决TopK问题，介绍如下。

2.2.经典解法介绍

创建数据量为 K 个的堆，将数据一条一条喂给Ta，无论数据总量多大，堆里永远只存着当前最佳的 K 个“候选人”。

2.3.大小堆选择

求最大的 K 个元素，维护一个小根堆： 根节点是堆中最小的元素，每当新元素到来，只要它比堆顶大，就替换掉堆顶，然后向下调整。这样堆里剩下的永远是最大的 K 个数据。 求最小的 K 个元素，维护一个大根堆： 根节点是堆中最大的元素，每当新元素比堆顶小，就替换掉堆顶，剩下的永远是最小的 K 个数据。

2.4.创建带有十万个随机数的文件

void CreateNData()
{
srand((unsigned int)time(NULL));
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}
int n = 100000;
for (int i = 0; i < n; i++)
{
int x = rand() + i;
fprintf(fin, "%d\\n", x);
}
fclose(fin);
}

srand((unsigned int)time(NULL)) 的作用是使 rand 函数每次运行时生成的随机数不同，下面将依次解释这几个函数的功能。

• rand()函数介绍 用于生成随机数，使用需要头文件 stdlib.h，不需要参数，返回值为一个伪随机数，范围在 0~RAND_MAX，其内部对一个叫"种子"的基准值进行运算生成随机数，且 rand 函数的默认种子是1。
• srand()函数介绍 srand 函数用于初始化随机数生成器(种子)，需要一个变化的参数，类型为无符号整型。
• time()函数介绍 time 函数用于返回一个时间戳，使用需要头文件 time.h，可以接收一个参数，返回值为一个时间戳，时间戳是一个数字，如果接收的参数为NULL，就只返回时间戳。

因此，将 time 函数的返回值转为无符号整型传入 srand 函数，就能使 rand 函数每次运行时生成的随机数不同。

用写的方式打开文件，判断是否打开成功，失败返回错误信息并退出，成功后继续使用 fprintf 函数以特定格式写入数据，最后关闭文件流。 注：rand 函数能产生的不重复随机数只有三万多，每次加 i 能减少重复量。

2.5.在电脑中找到数据文件

由于写操作会创建文件后写入，且打开文件时的路径为当前目录下的相对路径，因此可以直接在同级目录中找到数据文件 data.txt。

2.6.TopK代码实现

void Test_TopK()
{
#创建数据
CreateNData();
int k = 0;
scanf("%d", &k);
int* kheap = (int*)malloc(sizeof(int) * k);
if (kheap == NULL)
{
perror("malloc fail");
exit(1);
}
#读取前k个数据
FILE* fout = fopen("data.txt", "r");
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &kheap[i]);
}
#建堆
for (int i = (k – 2) / 2; i >= 0; i—)
{
ADJustDown(kheap, k, i);
}
#依次用堆顶数据比较文件的剩余数据
int x = 0;
while (fscanf(fout, "%d", &x) > 0)
{
#剩余数据大于堆顶数据
if (kheap[0] < x)
{
#替换堆顶数据并向下调整
kheap[0] = x;
ADJustDown(kheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", kheap[i]);
}
printf("\\n");
free(kheap);
}

动态接收想获取的数据个数 K，创建堆空间后，先从文件中读出 K 个数据到数组中并建堆，再依次从文件中将每个数据读出并与堆顶的数据比较判断，直到文件中的所有数据都被遍历判断后终止，打印结果并释放堆空间。

3.其他应用场景简介

1.图算法中的最短路径与最小生成树 简介：Dijkstra 算法和 Prim 算法均利用优先队列来快速抽取当前距离最小或权值最小的顶点，从而将复杂度从 O(V²) 优化至 O((V+E)*logV)。 2.中位数维护与数据流统计 简介：使用两个堆(大根堆存较小一半，小根堆存较大一半)，可以 O(logN) 地动态维护数据流的中位数，类似思想还可用于求百分位数等。 3.定时器与事件驱动 简介：很多定时器实现使用小根堆，以最近超时时间作为键，便于快速获取下一个到期事件。

四、总结

1.一份测试代码

包含堆的各项操作，堆排序和TopK问题的完整测试代码。

void Test_Heap()
{
int a[10] = { 4, 2, 8, 1, 5, 6, 9, 7 };
HP hp;
#初始化测试
HPInit(&hp);
#遍历插入数组中的值，排成小堆
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
#添加数据测试
HPPush(&hp, a[i]);
}
#判断是否为空测试
while (!HPEmpty(&hp))
{
#获取堆顶元素测试
printf("%d ", HPTop(&hp));
#删除数据测试
HPPop(&hp);
}
printf("\\n");
#销毁堆测试
HPDestroy(&hp);

#堆排序测试
HeapSort(a, sizeof(a) / sizeof(a[0]));

#TopK问题测试
Test_TopK();
}

2.整体总结

➤堆作为一种基于完全二叉树的优先级容器，以其简洁的数组存储和高效的对数级操作，成为计算机科学中最实用的数据结构之一。它的核心在于“有序的父子关系”而非“全局有序”，这种局部有序性恰好满足了大多数场景下“只关心极值”的需求。 ➤最后，堆并非万能，查找操作需要 O(N)，因不支持随机访问，也不适合频繁修改非堆顶元素。了解其优势与局限，才能在实际开发中做出正确的选择。

⚛️EL PSY CONGROO，十分感谢你的阅读

本期不确定： 是否应该补充向上调整建堆算法的时间复杂度数学分析