企业官网建设流程全解析

前言

——在计算机科学中，堆（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语言标准库函数，用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统（0or EXIT_SUCCESS表示成功，-1or EXIT_FAILURE表示失败）。
• 布尔值
  C语言并不自带布尔值作为内置数据类型，使用需引入标准库<stdbool.h>
• 交换函数
  C语言并不自带交换函数，需手动实现，其中的数据类型 HPDataType 为手动定义的堆存储数据类型。

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

2.头文件内容总览

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

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>#include<time.h>#TopK问题生成随机数据需要typedefintHPDataType;typedefstructHeap{HPDataType*arr;#存储堆节点的数组intsize;intcapacity;}HP;#初始化堆voidHPInit(HP*php);#添加数据voidHPPush(HP*php,HPDataType x);#删除数据voidHPPop(HP*php);#获取堆顶元素 HPDataTypeHPTop(HP*php);#判断是否为空 boolHPEmpty(HP*php);#销毁堆voidHPDestroy(HP*php);

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

3.初始化堆

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

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

4.判断空间容量

voidHPCheckCapacity(HP*php){if(php->size==php->capacity){intnewcapacity=(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.添加数据

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

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

6.向上调整算法

voidADJustUp(HPDataType*arr,intchild){#孩子对应的父亲下标intparent=(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.删除数据

voidHPPop(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.向下调整算法

voidADJustDown(HPDataType*arr,intn,intparent){#假设左孩子比右孩子小intchild=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.获取堆顶元素

HPDataTypeHPTop(HP*php){assert(php&&php->size);returnphp->arr[0];}

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

10.判断是否为空

boolHPEmpty(HP*php){assert(php);returnphp->size==0;}

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

11.销毁堆

voidHPDestroy(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(inti=1;i<size;i++){AdjustUp(arr,i);}

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

1.1.3.向下调整建堆

#方法二：向下调整建堆，时间复杂度为O(N)for(inti=(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)intend=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.创建带有十万个随机数的文件

voidCreateNData(){srand((unsignedint)time(NULL));FILE*fin=fopen("data.txt","w");if(fin==NULL){perror("fopen fail");return;}intn=100000;for(inti=0;i<n;i++){intx=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代码实现

voidTest_TopK(){#创建数据CreateNData();intk=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(inti=0;i<k;i++){fscanf(fout,"%d",&kheap[i]);}#建堆for(inti=(k-2)/2;i>=0;i--){ADJustDown(kheap,k,i);}#依次用堆顶数据比较文件的剩余数据intx=0;while(fscanf(fout,"%d",&x)>0){#剩余数据大于堆顶数据if(kheap[0]<x){#替换堆顶数据并向下调整 kheap[0]=x;ADJustDown(kheap,k,0);}}for(inti=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问题的完整测试代码。

voidTest_Heap(){inta[10]={4,2,8,1,5,6,9,7};HP hp;#初始化测试HPInit(&hp);#遍历插入数组中的值，排成小堆for(inti=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，十分感谢你的阅读

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