介绍

堆（Heap） 是一种特殊的 完全二叉树 数据结构，通常用于实现优先队列和高效排序（如堆排序）。

什么是堆

设有 n 个元素的序列 {K1，K2，... ，Kn}，当且仅当满足下述关系之一时，称之为堆：

满足 K_i <= K_{2i} 且 K_i <= K_{2i+1} ，此时叫 小顶堆（小根堆，Min Heap）。
满足 K_i>=K_{2i} 且 K_i >= K_{2i+1} ，此时叫 大顶堆（大根堆，Max Heap）。

提示：其中 2i 和 2i+1 应不大于 n

提示： 元素 K_i、K_{2i}、K_{2i+1} 的关系如下：

结构性质

堆是一棵 完全二叉树。

除了最后一层，其他层的节点都是满的。
最后一层的节点都靠左排列。
这种结构非常适合用数组来存储。

堆的存储

因为堆是完全二叉树，可以用数组存储：

假设数组索引从 0 开始，对于任意节点 i：

父节点：(i - 1) // 2
左孩子：2 * i + 1
右孩子：2 * i + 2

例子

数组 [10, 7, 6, 3, 5] 表示的大顶堆：

构造堆

首先找到最后一个节点的父节点，将父节点和2个子节点视为一个堆
如果叶子节点的值大，就与父节点交换位置
从后往前依次对每个堆进行步骤2的操作

例子

原始数据为 {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，根据该数据建大顶堆

对应的完全二叉树如下图所示：

最后一个节点为 7，其父节点为 16，从 16 这个节点开始构造最大堆；
构造完毕之后，从后往前到下一个父节点 2，直到所有父节点都构造完毕。

时间复杂度

O(n)

计算

用一棵高度为 4 层的满二叉树（n = 15），展示计算过程

              [A]               第 0 层 (根)
         /          \
      [B]            [C]        第 1 层
    /    \         /     \
  [D]    [E]     [F]     [G]    第 2 层
 /  \   /  \    /  \    /  \
[H][I][J][K] [L][M] [N][O]      第 3 层 (叶子)

第 0 层：1 个节点
第 1 层：2 个节点
第 2 层：4 个节点
第 3 层：8 个节点（叶子，不移动）

第 0 层（根）：
要沉到第 3 层 → 最多走 3 步
```
[A] → 第1层 → 第2层 → 第3层 (3步)
```

第 1 层（B、C）：
要沉到第 3 层 → 最多走 2 步

[B] → 第2层 → 第3层 (2步)
[C] → 第2层 → 第3层 (2步)

第 2 层（D、E、F、G）：
要沉到第 3 层 → 最多走 1 步

[D] → 第3层 (1步)
[E] → 第3层 (1步)
... 共 4 个节点，各 1 步

第 3 层（叶子）：
已经在最底层 → 走 0 步

总步数 = 各层节点数 × 每节点步数

第 0 层：1 节点 × 3 步 = 3
第 1 层：2 节点 × 2 步 = 4
第 2 层：4 节点 × 1 步 = 4
第 3 层：8 节点 × 0 步 = 0

总步数 = 3 + 4 + 4 = 11 步

n = 15，总步数 ≈ 11 ≈ n，所以建堆是 O(n)。

应用场景

堆能实现的功能，一般用数组也能实现，主要区别在插入、删除非最值元素的效率上：

堆牺牲了 “全序性”，只保证堆顶是最值，换来 插入 / 删除 的 O (\log n) 高效
有序数组是严格全序，但 插入 / 删除 要移动元素，效率仅 O (n)

优先队列（Priority Queue）

堆最经典、最基础的应用：

需要按“优先级”而非“先来先服务”处理任务（每次取堆顶就是当前优先级最高/最低元素。）

操作系统进程调度（高优先级进程优先执行）
网络数据包调度（QoS 保证）
事件驱动系统中的事件优先级队列

2. Top-K 问题（求前 K 大/前 K 小）

从海量数据中找出最大/最小的 K 个元素。

求前 K 大：用小顶堆，堆大小固定为 K，遍历数据时维护堆顶为当前第 K 大。
求前 K 小：用大顶堆，堆顶为当前第 K 小。

时间复杂度：O(n \log_2K)，远优于排序 O(n log n)。

例子：

热门榜单：热搜前 10、播放量前 100
日志/监控：找出访问量最高的 IP、错误最多的接口

3. 堆排序（Heap Sort）

需要稳定、原地、时间复杂度确定的排序。

特点：

时间复杂度：O(n log n)（最坏/平均/最好都一样）
空间：可做到原地排序（O(1) 额外空间）

适用：对内存敏感、要求排序性能稳定的场景。

总结

堆 = 完全二叉树 + 堆序性质。
大顶堆：父 ≥ 子，堆顶最大。
小顶堆：父 ≤ 子，堆顶最小。
核心操作是堆化，保证了高效的 O(log n) 调整。

原文出处：/show_1GW2iX24hVDb.html

数据结构：堆

介绍