数据结构堆的深度解析：为什么它是高效处理最值问题的利器

Ne0inhk

23 Mar 2026 — 14 min read

前言

在非线性数据结构的家族中，堆是兼具 “完全二叉树特性” 与 “最值优先级” 的高效工具 —— 它以数组为物理载体，却暗藏树形逻辑，能在 O (1) 时间获取最值，O (logN) 时间完成插入删除，成为解决排序、Top-K 等经典问题的 “一把好手”。

📚 初阶数据结构

一、堆的核心概念与结构特性

堆的本质是满足特定规则的完全二叉树，同时通过数组存储以最大化空间利用率（用连续数组存储完全二叉树，无需额外存储指针（链表存树的方式会浪费指针空间），几乎没有内存浪费）。

1. 堆的定义

堆就是这么个东西：

看着像一棵 “层层填满、最后一层靠左排” 的树（完全二叉树），但实际是存在连续数组里的；
有个铁规矩：要么每个节点都比自己的子节点大/相等（这叫大根堆，最顶上的是最大的数），要么每个节点都比自己的子节点小/相等（这叫小根堆，最顶上的是最小的数）；
核心用处就是快速找最大 / 最小数，不用挨个遍历，直接拿最顶上的就行。

2. 核心特性

逻辑结构：必为完全二叉树，不存在 “断层” 节点，所有叶子节点集中在最后两层，且最后一层节点靠左排列；

存储结构：物理上是连续数组，通过索引映射父子关系（设节点索引为i）：

父节点索引：( i - 1) / 2（向下取整）；左子节点索引：2 * i + 1；右子节点索引：2 * i + 2；

最值特性：堆顶（数组第一个元素）始终是集合中的最大值（大根堆）或最小值（小根堆）。

3. 直观示例

小根堆：逻辑上根节点最小，数组存储为 [10, 15, 25, 56, 30, 70]；

大根堆：逻辑上根节点最大，数组存储为 [70, 56, 30, 15, 25, 10]。

二、堆的实现

1、堆的结构

堆的底层是用数组实现的，因此它的结构和顺序表的结构基本一致，具体定义如下：

typedef int HpDataType; typedef struct Heap { HpDataType* a; int size; int capacity; }heap;

2、堆的初始化

//初始化堆 void HeapInit(heap* php) { assert(php); php->a = (HpDataType*)malloc(sizeof(HpDataType) * 4); if (php->a == NULL) { perror("malloc"); return; } php->capacity = 4; php->size = 0; }

3、堆的销毁

//堆的销毁 void HeapDestroy(heap* php) { assert(php); free(php->a); php->a = NULL; php->capacity = php->size = 0; }

4、堆的插入（含向上调整算法）

入堆的操作逻辑很简单：先把新数据直接插入到堆的末尾（对应数组的最后一个位置），插入后如果堆的结构不符合小根堆 / 大根堆的规则，就通过向上调整算法，把这个新元素逐步 “往上挪”，直到它处于一个能让整个堆重新满足规则的位置

//入堆 void HeapPush(heap* php, HpDataType x) { assert(php); //扩容 if (php->capacity == php->size) { HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType) * php->capacity * 2); if (tmp == NULL) { perror("realloc"); return; } php->a = tmp; php->capacity = 2 * php->capacity; } php->a[php->size] = x; php->size++; //向上调整 AdjustUp(php->a, php->size - 1); }

新数据插入堆尾的操作，本质上就是顺序表的尾插（这部分内容我们在之前的文章里已经讲过啦），所以这一部分我重点讲向上调整算法的思路

【向上调整算法】：

//交换算法 void swap(HpDataType* p1, HpDataType* p2) { HpDataType x = *p1; *p1 = *p2; *p2 = x; } //向上调整 void AdjustUp(HpDataType* a, int child) { //计算父节点的索引 int parent = (child - 1) / 2; // 循环条件：child > 0 表示当前节点还没到堆顶（堆顶节点的child为0，无父节点） // 只要没到堆顶，就持续检查当前节点与父节点是否符合堆的规则 while (child > 0) { //孩子小于父亲就交换值 if (a[child] < a[parent]) { swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } //符合堆的规则就跳出循环 else { break; } } }

这段向上调整算法是针对小根堆设计的；如果要适配大根堆，只需要把判断条件改成 “子节点值大于父节点” 即可。

5、堆的删除（含向下调整算法）

堆的删除操作是针对堆顶元素的，具体逻辑是：先把堆顶元素和堆的最后一个元素交换位置，接着删除数组末尾（原堆顶元素），最后对新的堆顶元素执行向下调整算法，让堆重新满足规则。

之所以不直接删除堆顶元素，是因为堆顶是堆的核心节点，直接删除会彻底打乱整个堆的父子节点逻辑，后续几乎无法恢复成合法的堆结构。

//出堆 void HeapPop(heap* php) { assert(php); assert(!HeapEmpty(php)); //删除数据 swap(&php->a[0], &php->a[php->size - 1]); php->size--; //向下调整 AdjustDown(php->a, php->size, 0); }

【向下调整算法】:

//交换算法 void swap(HpDataType* p1, HpDataType* p2) { HpDataType x = *p1; *p1 = *p2; *p2 = x; } //向下调整 void AdjustDown(HpDataType* a, int n, int parent) { int child = 2 * parent + 1;//假设左孩子小 while (child < n) { //选出孩子中小的那一个 if (child + 1 < n && a[child + 1] < a[child])//避免越界访问 { ++child;//假如右孩子小，child++ } if (a[child] < a[parent]) { swap(&a[child], &a[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }

这段代码实现的是小根堆的向下调整逻辑。如果要适配大根堆的出堆操作，只需要把两处判断条件的符号修改为 “大于” 即可：

子节点选择部分：将 a[child + 1] < a[child] 改为 a[child + 1] > a[child]（选出子节点中更大的那个）；父子节点交换部分：将 a[child] < a[parent] 改为 a[child] > a[parent]（若子节点值大于父节点，执行交换）。

【向下/向上调整算法时间复杂度计算】

1、向上调整的过程，是从堆的某个叶子节点（新插入节点）向堆顶移动，调整的次数由堆的高度决定。

2、由于堆是完全二叉树结构，若堆的元素个数为 n，则完全二叉树的高度为 log2（N + 1）

3、因此，向上调整算法的时间复杂度为 O（logN）（在数据结构中log以2为底N的对数可以写作O（logN））

（向下调整算法的时间复杂度逻辑一致：从堆顶向叶子节点移动，最大次数也是树的高度，复杂度同样为 O（logN）

6、堆的判空、元素个数、取堆顶元素接口

//取堆顶元素 HpDataType HeapTop(heap* php) { assert(php); return php->a[0]; } //判空 bool HeapEmpty(heap* php) { assert(php); return php->size == 0; } //堆元素个数 int HeapSize(heap* php) { assert(php); return php->size; }

三、堆的应用

1、堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？

① 向下调整建堆

向下调整建堆逻辑：这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆；

// n: 数组中元素的总个数 // 核心逻辑：从最后一个非叶子节点开始，向前逐个调整节点，使每个子树满足堆的性质 // 最后一个非叶子节点的下标计算： // 数组下标从0开始时，最后一个元素的下标是n-1，它的父节点下标为 (n-1-1)/2 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { // 对下标为i的节点进行"向下调整"，使以i为根的子树成为堆 AdjustDown(a, n, i); }

② 向上调整建堆

向上调整法建堆：从第 2 个元素（i=1）开始，逐个对每个元素调用 AdjustUp，让新元素向上和父节点比较、交换，直到满足堆的性质，最终把整个数组建成堆；

//建堆 -- 向上调整建堆 for (int i = 1; i < n; i++) { AdjustUp(a, i); }

我就不画图展示啦，这个过程其实相当于模拟堆的插入操作：每往堆里加入一个新元素，就对它做一次向上调整；等所有元素都插入并调整完毕，整个堆也就构建完成了。

【建堆时间复杂度分析】

向下调整建堆：O (N)

向上调整建堆：O（N * logN）

核心差异：

1、向上调整建堆：低层（数量多）+ 调整次数多（底层节点要逐层往上调，最多需 logN 次），最终总代价是 “大量节点 × 多次调整”→ O (N logN)。

2、向下调整建堆：高层（数量少）+ 调整次数多（根节点要逐层往下调，最多需 logN 次）；

低层（数量多）+ 调整次数少（底层节点基本不用调），最终总代价是 “少量节点 × 多次调整 + 大量节点 × 少量调整”→ O (N)。

2、堆排序

堆排序（升序）思想：先建大顶堆（堆顶是最大值），再反复将堆顶与堆尾交换（最大值归位），然后调整剩余元素为大顶堆，直到堆空，数组升序

//排升序 建大堆 O(N*logN) void HeapSort_Up(int *a, int n) { //建堆 -- 向下调整建堆 -- O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } int end = n - 1; //排序 -- O(N*logN) while (end > 0) { swap(&a[end], &a[0]); AdjustDown(a, end, 0); end--; } }

拍降序的话，建小顶堆就行：堆顶始终是当前堆的最小值，把它和堆尾元素交换（最小值就放到了当前未排序区的末尾，逐步归位），再将剩下的元素重新调整为小顶堆，重复这个过程，直到堆处理完，数组就降序排好了。

//排降序 建小堆 O(N*logN) void HeapSort_Down(int* a, int n) { //建堆 -- 向上调整建堆 -- O(N*logN) for (int i = 1; i < n; i++) { AdjustUp(a, i); } int end = n - 1; //排序 -- O(N*logN) while (end > 0) { swap(&a[end], &a[0]); AdjustDown(a, end, 0); end--; } }

3、TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1、用数据集合中前K个元素来建堆前k个最大的元素，则建小堆前k个最小的元素，则建大堆

2、用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

//TOP-K 求前k个最大/最小的元素 //前k个最大的元素，则建小堆 //前k个最小的元素，则建大堆 //当前 n = 15; k = 10; //求前10个最大的元素： void TOP_K() { //造数据 int n = 15; int* a = (int*)malloc(sizeof(int) * n); srand((unsigned int)time(NULL)); for (size_t i = 0; i < n; ++i) { a[i] = rand() % n + 1; } int k = 10; //向下调整建堆 -- 建小堆 for (int i = (k - 1 - 1)/ 2; i >= 0; i--) { AdjustDown(a, 10 ,i); } //接下来剩下的元素和堆顶的元素进行比较 for (int i = k; i < n; i++) { if (a[0] < a[i]) { swap(&a[0], &a[i]); //向下调整 AdjustDown(a, 10, 0); } } //打印所有数据，观察是否满足 for (int i = 0; i < n; i++) { printf("%d ",a[i]); } }