一、起源:按优先级取元素的需求

1.1 先后顺序不足以表达处理次序

队列把处理次序固定为到达次序,这一承诺适用于排队、削峰与按层展开。但有一类问题不关心到达顺序,只关心"当前哪一个最该被处理":

  • 任务调度。就绪队列中等待运行的任务带有优先级,每次需要挑出优先级最高(或虚拟运行时间最小)的一个执行。
  • 事件处理。离散事件仿真、网络事件循环、告警收敛都按事件的时刻或严重级别处理,而不是按事件产生的时间先后。
  • 最值维护。从海量数据中持续取出最大或最小的若干个元素,例如榜单的 Top K、词频统计、多路合并时的当前最小值。
  • 最短路与最小生成树。Dijkstra 与 Prim 的主循环都是"从尚未确定的顶点中取出当前距离最小的一个"。

这些场景的共同结构是插入与取出不对称:元素可以频繁插入,而取出只关心"当前最优的那一个"。到达顺序对结果没有意义,关键字的大小才是次序依据。

1.2 用完全有序维护最值的代价

最直接的做法有两种,代价都不理想。

每次取出前重新排序。 排序一次是 O(n log n),若每取一个元素都排序一次,取出 k 个元素的代价是 O(k·n log n)。即使只排一次然后按下标依次取,单次取出的代价是 O(1),但排序本身付出了维护全部 n 个元素相对次序的成本。

每次线性扫描找最值。 插入 O(1),取最值 O(n)。取出 k 个元素的总代价是 O(k·n)。选择排序正是这一模式的体现:每一轮线性扫描找最小元,总代价 O(n²),其中绝大部分开销花在查找而非交换上。

两种做法的共同问题是维护了超出需求的信息:需求只要求"最值可查",排序却确定了任意两个元素之间的先后关系。n 个元素的全序包含 O(n log n) 量级的信息,而"取出最大元"只需要知道哪一个是最大元。多余的信息必须被维护,这就是代价的来源。

1.3 部分有序的思路

把承诺收窄到只保证必要的不变式:

  • 堆顶必须是最值,这样取最值的代价是 O(1);
  • 每个节点与其子节点之间满足偏序关系(父不小于子,或父不大于子),这是维持"堆顶是最值"所需的最小约束;
  • 兄弟节点之间、不同分支之间不作任何约束。

约束变弱,违反约束的情况在插入与删除时就容易修复:一次修改至多影响从根到叶的一条路径,代价为 O(log n)。这就是堆的基本设计。它用一条从根到叶的单调路径代替了整棵树的有序性,把 O(n log n) 的全局维护降为 O(log n) 的局部调整。

为了进一步降低存储代价,堆用完全二叉树作为形状约束:完全性使树的高度保持在 O(log n),同时让层序编号与数组下标一一对应,从而可以用数组存储而不需要任何指针。

1.4 抽象数据类型视角

优先队列(priority queue) 是这里要实现的抽象数据类型,它的语义是"每次取出的元素是当前优先级最高(或最低)的一个",与插入顺序无关;堆是它的实现之一,也是最常用的一种。堆与优先队列的关系,相当于数组与线性表、哈希表与映射的关系:前者是存储在内存中的具体结构,后者是描述操作与语义的规范,这层区分见 抽象数据类型(ADT)。

由此可以确定本文的边界:

  • 需要了解优先队列对外承诺什么、如何选择实现,属于语义与选型问题;
  • 需要了解堆内部如何维持最值在顶部、各种操作如何调整,属于结构与算法问题;
  • 优先队列与普通队列的关系(都是出队语义,差别只在决定出队顺序的依据)已在 栈与队列 中给出。

从操作集的复杂度开始,堆的位置会很清晰。


二、原理

2.1 优先队列的语义

2.1.1 操作集

操作 语义 备注
offer(e) / insert(e) 插入元素 元素必须可比较
peek() / findMin() 读取最值,不移除 只读操作
poll() / deleteMin() 移除并返回最值 最核心的取出操作
size() / isEmpty() 元素个数与判空 O(1)
decreaseKey(i, k) / increaseKey(i, k) 修改指定元素的关键字 需要先定位该元素,非标准接口
remove(i) 删除指定元素 同上
merge(h) 合并两个优先队列 二叉堆的实现代价为 O(n1+n2)

"最值"的具体方向由比较器决定:默认取最小值的称为小顶堆语义,默认取最大值的称为大顶堆语义。语义本身与实现无关,同一份堆代码换个比较器就切换方向。

decreaseKey 与 remove 出现在操作集中,但它们不是所有实现都能高效支持,这一差别是后文多种堆变体的直接来源(2.5 节)。

2.1.2 实现候选的复杂度对照

实现 插入 取最值 删除最值 建堆 能否快速定位任意元素
无序数组 O(1) O(n) O(n) O(1) O(n)
无序链表 O(1) O(n) O(n) O(1) O(n)
有序数组(升序,最小值在头部) O(n) O(1) O(n) O(n log n) O(log n)
有序链表(升序) O(n) O(1) O(1) O(n log n) O(n)
二叉堆 O(log n) O(1) O(log n) O(n) O(n)
平衡二叉搜索树 O(log n) O(log n) O(log n) O(n log n) O(log n)
斐波那契堆 均摊 O(1) O(1) 均摊 O(log n) O(n) O(n)

三点结论:

  1. 插入与取最值必须有一端付出对数代价。无序结构把代价放在取最值上,有序结构把代价放在插入上;只有树形结构能让两端都落在 O(log n) 量级。堆的取舍是在这两端之间取折中,代价是放弃"查找任意元素"与"有序遍历"。
  2. 有序数组的删除代价取决于最值的存放位置。把最小值放在头部时删除需要搬移 O(n);改为按降序存放(最小值在末尾)则删除是 O(1),但插入仍需 O(n) 定位与搬移。这类"换个存放方向"的调整只改变常数与常数项归属,不改变量级。
  3. 堆不是唯一选择。若还需要按键查找、删除任意元素与有序遍历,平衡二叉搜索树(或跳表)能同时提供这些能力,代价是更高的单元素内存开销与更大的常数因子;只要"取最值"一个需求,堆是最省的方案。按键定位的复杂度对照见 散列表,有序结构的另一种选择见 跳表,各容器的复杂度总表见 Java 集合框架实现原理。

2.2 完全二叉树与数组表示

2.2.1 完全二叉树的性质

完全二叉树指:除最后一层外每一层都被节点填满,最后一层的节点从左向右连续排列(中间不留空位)。

由此得到堆所依赖的两条性质:

  1. 高度为 ⌊log₂n⌋。因为每一层都尽量填满,n 个节点的树高与 log n 同阶。任意形状的二叉树则可能退化为链,高度为 n。
  2. 层序编号连续。按层、每层从左到右依次编号,得到的编号序列正好是不重复的 0 到 n−1,中间没有空缺。这是数组表示能够成立的前提:数组的一个下标恰好对应树中的一个节点,不存在"编号跳号"造成的空洞。

需要与满二叉树区分:满二叉树要求每一层都填满,节点数为 2^h−1;完全二叉树允许最后一层不满,只要求不满的部分集中在右侧。完全二叉树的性质、高度与节点数的关系、数组表示下的下标算术见 二叉树与二叉搜索树。

2.2.2 下标关系

以下标从 0 开始为例,节点 i 的父子关系为:

                0
             /     \
          1           2
        /   \       /   \
       3     4     5     6
      / \   /
     7   8 9
数组:[0][1][2][3][4][5][6][7][8][9]
关系 下标从 0 开始 下标从 1 开始
父节点 (i - 1) / 2 i / 2
左孩子 2 * i + 1 2 * i
右孩子 2 * i + 2 2 * i + 1
第一个叶子节点 n / 2 n / 2 + 1
最后一个非叶节点 n / 2 - 1 n / 2

表中的除法均为整除。两种编号方式在实现上都可用,区别是 0 起始的父节点计算多一次减法,而 1 起始会把数组的第 0 个槽位闲置;主流标准库(Java、Python、C++ 的堆相关实现)采用 0 起始。

派生结论:

  • i >= n / 2 的节点一定是叶子,i < n / 2 的节点一定有左孩子。这使下沉可以先用 i < n / 2 判断是否需要继续(3.1 节代码中的 half)。
  • 左孩子存在不保证右孩子存在:2i+2 < n 需要单独判断,这是下沉里最容易漏掉的边界。

2.2.3 为什么用数组存储

定位父子节点只需算术运算。 给定下标即可算出父与子,不需要存储任何链接,因此没有指针字段、没有节点对象头、也没有为"向上调整"额外维护父指针的必要。链式实现要支持上浮,必须每个节点多存一个父引用,否则只能从根重新搜索。

没有空洞。 完全性保证 n 个元素恰好占据数组的前 n 个位置。链式存储中大量为空的子指针在完全二叉树下虽然也不出现,但每个节点独立的分配开销依然存在。

缓存友好。 同一层的节点在数组中相邻,父子下标之间的跨度随层数增长但始终是可预取的;一次缓存行可以覆盖同一层或相邻层的多个节点。链式实现的节点分散在堆内存中,每次跳转都可能缓存未命中。数组连续存储与缓存局部性的机制、以及"随机访问"的准确含义见 数组与链表。

例外情形。 需要合并两个堆(2.5.4 节)或需要按外部下标定位元素(2.5.1 节)时,完全性这一形状约束反而成为障碍:合并会破坏"层序连续"的条件,而数组无法局部地表达合并后的新形状。这些场景改用链式节点或配合辅助数组,代价是回到指针开销与较差的缓存行为。

2.3 堆序性质与操作

2.3.1 堆序性质

大顶堆(max-heap):每个节点的关键字不小于其子节点的关键字,堆顶为全局最大值。
小顶堆(min-heap):每个节点的关键字不大于其子节点的关键字,堆顶为全局最小值。

堆序性质只约束父子关系,其等价表述是:从根到任意叶的路径上,关键字单调不减(或单调不增)。它不约束兄弟节点、不约束左右子树之间的大小关系,因此:

  • 堆不是二叉搜索树。搜索树要求左子树全部小于根、右子树全部大于根;堆对左右子树的大小关系没有任何要求,相等的键也可以出现在任意位置。
  • 堆不是完全有序。除沿路径的偏序外,元素之间没有确定的先后关系,迭代优先队列得到的顺序通常不是出队顺序。
  • 堆顶是最值,其他元素的位置只有偏序意义。数组下标 i 处的元素保证了"不小于其祖先、不大于其子孙",除此之外没有任何承诺。

由此推出三条操作代价特征:取最值 O(1),插入与删除最值 O(log n),而查找任意元素只能扫描,代价 O(n)。

2.3.2 上浮(sift-up / swim)

场景:插入元素。

  1. 把新元素放到数组末尾。此时完全性仍然成立(新节点补在最后一层的下一个位置),但堆序可能被破坏——新元素可能小于它的父节点(小顶堆)。
  2. 把新元素与父节点比较,若违反堆序则交换位置,然后继续与新的父节点比较。
  3. 重复直到到达根(i == 0)或父节点已满足堆序。
小顶堆插入 2(数组 [1, 3, 5, 7, 4] → 追加 2 后再调整)

  追加到末尾:            与父比较交换:          与父比较交换:
        1                       1                       1
      /   \                   /   \                   /   \
     3     5                 3     5                 2     5
    / \   /                 / \   /                 / \   /
   7   4 2                 7   4 2   (2 < 5)        7   4 3   (2 < 3)

  每上升一层只需与唯一的一个父节点比较,不存在选择分支。

复杂度 O(log n):每次交换上升一层,层数不超过树高 ⌊log₂n⌋。

上浮过程只有"与父节点比较"这一个决策,因此代码结构简单;它的代价在于待调整元素可能从叶子上浮到根,路径长度为 O(log n)。

2.3.3 下沉(sift-down / sink)

场景:删除最值。

  1. 记录堆顶元素(即最值),把数组末尾元素搬到堆顶位置,元素个数减一。此时完全性成立,但堆序可能被破坏——末尾元素通常较小,放在根上可能小于子节点。
  2. 从根开始,与两个孩子中更优先的那个比较,若违反堆序则交换,然后继续在下一层比较。
  3. 重复直到到达叶子(孩子下标越界)或已满足堆序。
大顶堆删除堆顶(数组 [9, 7, 8, 3, 4, 5] → 取走 9,末尾 5 提到根再下沉)

  取走堆顶,末尾上位:      与较大的孩子比较交换:     继续比较:
        5                       8                       8
      /   \                   /   \                   /   \
     7     8                 7     5                 7     5
    / \   /                 / \                     / \
   3   4 5                 3   4                   3   4

  (5 与右孩子 8 交换)       (5 与两个孩子中较大的 7 比较,5 < 7,交换)

必须与两个孩子中更优先的一个比较。若只与左孩子比较,可能出现这样的情况:根为 5,左孩子为 3,右孩子为 9;与左孩子比较后发现 5 > 3,判定堆序成立而停止,但 9 被留在根的孩子位置,堆序实际已被破坏。这类缺陷不会立即报错,只在后续出队时表现为"取出的不是最值"。

复杂度 O(log n),每层一次交换,最多下沉到叶子。

空穴法(hole)实现。每次交换需要三次赋值(临时变量、两次写入),改为把待下沉元素暂存,沿途把更优的子节点直接上提到空位,最后把元素落到最终位置:每层只需一次赋值,取值也可减少一次数组访问。

2.3.4 插入与取堆顶

操作 步骤 复杂度
peek() 返回 items[0],需先判空 O(1)
offer(e) 追加到末尾 + 上浮 O(log n)
poll() 记录 items[0],末尾元素搬到根,个数减一,下沉 O(log n)
size() / isEmpty() 读取字段 O(1)

两种操作的形状是"一端进、另一端出":插入发生在数组末尾,取出发生在数组开头。这与队列的头尾分工相似,但决定谁在堆顶的规则不同——队列按到达时间,堆按关键字大小。

2.3.5 建堆的两种方式

方式一:逐个插入。 依次把元素 offer,每次上浮。

  • 单次上浮的代价取决于元素当前所在的层,越靠近根代价越小。
  • 最坏情况是 O(n log n):例如向小顶堆依次插入递减序列,每个新元素都成为新的最小值,每次都要上浮到根。
  • 平均情况更接近线性:随机输入下新元素平均只需上升常数层,工程中常见的估计是 1.5 到 2 层,因此逐个插入的实际耗时远低于最坏界。但最坏界仍是 O(n log n),不能用在需要严格界的分析中。

方式二:自底向下沉(heapify)。 把 n 个元素原样放入数组(此时只保证完全性,堆序完全未建立),从最后一个非叶节点 n/2 - 1 开始,按下标递减到 0,对每个节点执行一次下沉。

O(n) 的推导:

高度为 h 的节点数      ≤ ⌈n / 2^(h+1)⌉        (完全二叉树下取等号)
高度为 h 的节点下沉代价 = O(h)                (最多下沉 h 层)
总代价                 = Σ(h = 0 ~ ⌊log n⌋) ⌈n / 2^(h+1)⌉ · O(h)
                      = O(n · Σ(h ≥ 0) h / 2^h)
                      = O(n · 2)              (级数 Σ h/2^h 收敛到 2)
                      = O(n)

推导的直观解释:代价高的节点数量很少。底层节点占据总数的一半左右,而它们下沉的代价为 0(已经是叶子);次底层占四分之一,代价为 1;再上一层占八分之一,代价为 2。按 1/2^h 递减的节点数乘以线性增长的代价,总和收敛到常数的 2 倍,而不是 log n 倍。这与动态数组按倍数扩容时"总复制量小于最终元素数"属于同一类级数收敛的摊还结论,级数与摊还分析的完整口径见 复杂度与算法分析。

两种方式的比较与选用:

维度 逐个插入 自底向下沉
时间 最坏 O(n log n),平均接近 O(n) 最坏与平均均为 O(n)
前提 元素逐个到达,可在任意时刻查询堆顶 必须一次性拿到全部元素
比较次数(估) 平均约 1.5n 次 约 2n 次
适用 在线插入,中途要读堆顶 批量初始化(构造函数传入集合)

因此标准库在接收集合进行初始化时使用方式二(Java 的 PriorityQueue(Collection) 内部执行 heapify),而逐个 add 走方式一。方式二不能用于在线场景的原因不是它不正确,而是它要求元素集合已确定;对已经建成的堆再整体重建一遍,代价是 O(n),而单次插入只需 O(log n)。

2.3.6 修改任意元素的前提

堆只保证堆顶可定位。若要把下标 i 处元素的关键字改大或改小,前提是已知它在数组中的下标。

知道下标后,修改的调整方向由关键字的增减决定:

  • 关键字变小(小顶堆):只可能违反与父节点的关系,因此只需上浮;
  • 关键字变大(小顶堆):只可能违反与子节点的关系,因此只需下沉。

两个方向不会同时违反,因此一次修改最多执行一次 O(log n) 的调整。上浮与下沉的开销同阶,合计仍是 O(log n)。

若只知道元素的值或引用,必须先扫描数组找到下标,代价 O(n)。这一条解释了为什么多数标准库不提供 decrease-key 接口:O(n) 的定位成本会吞掉 O(log n) 的调整收益,与其提供一个看起来高效实则线性扫表的接口,不如让使用者自行决定定位方式。

两个必须注意的陷阱:

  1. 元素对象被就地修改。堆中保存的是引用时,外部修改对象的比较字段不会通知堆,堆序被破坏且没有任何报错。此后 peek() 返回的可能不再是真正的最值。Java 的 PriorityQueue 与 C++ 的 priority_queue 都有这一性质。
  2. 相等关键字与修改的配合。若比较器只比较关键字,修改后与旧值相等,调整方向无从判断;此时按"等于即视为满足堆序"处理是可以的(堆序允许相等),但要确认比较器的一致性。

索引堆通过增加反向索引把定位降为 O(1),使 decrease-key 成为 O(log n) 的完整操作(2.5.1 节)。

2.4 堆排序

2.4.1 流程

以升序排序为例,全程在原数组上进行:

  1. 建堆:对数组执行自底向下沉,得到大顶堆,代价 O(n)。
  2. 逐个取出最大值:重复 n−1 次——
  • 把堆顶(当前堆内最大值)与堆的最后一个元素交换;
  • 堆的逻辑大小减一(最后一个元素已就位,不再参与);
  • 对新的堆顶执行下沉,恢复堆序。
  1. 结束时数组从后向前依次被填入由大到小的元素,整体升序。
数组 [4, 7, 2, 9, 1] → 建大顶堆 [9, 7, 2, 4, 1]

第 1 轮:交换堆顶与末尾 (9, 1) → [1, 7, 2, 4 | 9],对长度 4 的堆下沉 → [7, 4, 2, 1 | 9]
第 2 轮:交换堆顶与末尾 (7, 1) → [1, 4, 2 | 7, 9],对长度 3 的堆下沉 → [4, 1, 2 | 7, 9]
第 3 轮:交换堆顶与末尾 (4, 2) → [2, 1 | 4, 7, 9],对长度 2 的堆下沉 → [2, 1 | 4, 7, 9]
第 4 轮:交换堆顶与末尾 (2, 1) → [1 | 2, 4, 7, 9],堆内只剩一个元素,结束

结果 [1, 2, 4, 7, 9]

为什么升序用大顶堆:每次取出的是当前最大值,把它交换到未排序部分的末尾,正好落在它最终应在的位置上(从后向前)。若升序用小顶堆,堆顶是最小值,无法直接放到末尾。

2.4.2 复杂度与特性

阶段 代价
建堆 O(n)
n−1 次"交换 + 下沉" O(n log n)
合计 O(n log n)
  • 时间上界有保证。最坏、平均都是 O(n log n),不存在快速排序那样的 O(n²) 退化输入。
  • 原地。除交换用的临时变量外不需要额外数组;若把下沉写成递归,则额外使用 O(log n) 的调用栈,因此实现上通常写成循环。
  • 不稳定。原因有两处:堆顶与末尾元素的长距离交换会跨越大量元素,破坏相等键原有的相对顺序;下沉过程中相等键的左右子树位置也不受约束。需要稳定排序时应选择归并排序或基于归并的 Timsort。

2.4.3 与快速排序、归并排序的对比

算法 平均 最坏 额外空间 稳定性 特点
堆排序 O(n log n) O(n log n) O(1) 不稳定 最坏有保证、原地;访问跳跃、常数因子较大
快速排序 O(n log n) O(n²) 平均 O(log n)(递归栈) 不稳定 平均最快、缓存友好;最坏输入需随机化或三数取中规避
归并排序 O(n log n) O(n log n) O(n) 稳定 稳定、可外部化;需要等长辅助数组(链表实现只需 O(log n) 栈)
插入排序 O(n²) O(n²) O(1) 稳定 小规模与近似有序时很快,常用作混合排序的收尾阶段

各算法的递归式、空间复杂度口径与比较排序的 Ω(n log n) 下界见 复杂度与算法分析;十类排序算法的实现要点、稳定性、适应性以及在规模与分布上的选型见 排序与查找。

堆排序与另外两者的差异还有一条实现层面的原因:堆的访问模式对缓存不友好。下沉时每层访问的下标跨度与前一层不同,且父子访问常落在不同的缓存行;快速排序的划分是顺序扫描,归并排序的合并也是顺序扫描。因此三者的量级相同,实测排序常数通常为快排 < 归并 < 堆排。

适用场景:

  • 内存受限且要求最坏时间有保证(嵌入式、内核、外部存储的原地排序);
  • 只需要部分有序的结果,例如取前 K 个元素——此时不必全排序(2.6.1 节);
  • 作为"最坏情况有保证"的备选:多数语言的标准排序用 Timsort(Java 对象数组、Python)或双轴快排(C++),堆排序的典型用途集中在部分排序与内存受限。

2.5 堆的变体

堆的每一次"变形"都对应一个具体操作代价过高的问题。以下变体按"补哪一个短板"排列。

2.5.1 索引堆:支持修改与删除任意元素

要补的短板:堆无法在 O(1) 内定位任意元素,因此 decrease-key 需要线性扫描(2.3.6 节)。

结构:用三个并行数组把"外部下标"与"堆中位置"分离。

数组 含义
data[i] 外部下标 i 对应的元素(关键字)
heap[p] 堆中第 p 个位置存放的是哪个外部下标
pos[i] 外部下标 i 当前在堆中的位置(−1 表示不在堆中)

不变式为两条互为逆映射的关系:heap[pos[i]] == i,pos[heap[p]] == p。交换堆中两个位置时,除了交换 heap 的两个值,还必须同步更新 pos,使两条关系继续成立。这是索引堆实现中最容易出错的一步:漏更新一处 pos 不会立即报错,而是在后续 change/remove 时定位到错误的元素。

操作与代价:

操作 流程 复杂度
insert(i, key) 追加到堆末尾,记录 pos[i],上浮 O(log n)
change(i, key) 改 data[i],按增减方向对 pos[i] 上浮或下沉 O(log n)
remove(i) 用堆末尾元素填补 pos[i] 位置,按与父节点的比较决定上浮或下沉 O(log n)
contains(i) 读 pos[i] 是否为有效值 O(1)
peek() / deleteMin() 与普通堆相同 O(1) / O(log n)

没有反向索引时的替代办法:线性定位后删除 O(n);或者把待删除元素改到极端值再 deleteMin(写法简单,代价是两次调整);或者标记删除并在取出时跳过(惰性删除,代价是堆中堆积无效元素)。批量删除多个元素后一次性重建一棵堆,代价 O(n),通常比逐个删除更省。

2.5.2 双堆(对顶堆):维护中位数

要补的短板:中位数是"中间位置"的统计量,单个堆只能维护一端。

结构:用两个堆把数据从中位数处切成两半。

  • 大顶堆 low 保存较小的一半,堆顶是这一半中的最大值;
  • 小顶堆 high 保存较大的一半,堆顶是这一半中的最小值。

需要维持两条不变式:

  1. 顺序不变式:low 中所有元素不大于 high 中所有元素。插入时先把新元素放入一侧,再把该侧的堆顶搬到另一侧,从而保证跨堆的顺序;
  2. 数量不变式:两堆大小之差不超过 1。

操作:插入 O(log n)(一次入堆 + 至多一次搬运);取中位数 O(1)——两堆大小相等时中位数为两个堆顶的平均值,否则为较大堆的堆顶。

变体与注意事项:

  • 维护第 k 大元素:把数量不变式改为"两堆大小之差固定为 k",堆顶即答案;
  • 滑动窗口中位数:窗口左移使元素过期,堆无法按键删除过期元素,需要惰性删除(堆中存 (值, 位置),出队时校验并丢弃),代价是堆中可能堆积过期元素;
  • 整数溢出的边界:(low.peek() + high.peek()) / 2.0 在接近整型上限时会溢出,应先用 long 或 double 中转。

2.5.3 d 叉堆:在插入与删除之间调比例

要补的短板:二叉堆的树高限制在 log₂n,插入与删除的做法无法按场景分别优化。

结构:每个节点有 d 个孩子(d 常取 4)。

关系(下标从 0 开始) 公式
父节点 (i - 1) / d
第 j 个孩子(j = 0 ~ d−1) d * i + j + 1

取舍:

  • 树高由 log₂n 降为 log_d n,上浮的层数减少,因此插入更快;
  • 下沉时每层要在 d 个孩子中找出最优先者,比较次数由 2 次增加到 d 次,总比较次数约为 d·log_d n,下沉变慢;
  • 每层的 d 个孩子存放在连续内存中,一次缓存行可以覆盖多个孩子,比较时的缓存未命中减少。

由此确定适用面:插入(或 decrease-key)远多于删除的场景更适合较大的 d;d = 2 即二叉堆;d 过大时下沉退化为在数组片段中线性查找最值,反而变慢。d = 4 是常见的折中取值。

2.5.4 可合并堆:左偏树与斜堆

要补的短板:合并两个二叉堆的代价是 O(n1+n2)。原因是完全性这一形状约束使数组无法局部拼接,只能把两个数组的元素合到一起再重建。

思路:放弃"完全二叉树 + 数组"的组合,改用链式节点。堆序性质不需要形状约束也能成立(只要每个节点与自己孩子满足偏序),于是合并可以通过拼接树的"右路径"完成。

左偏树(leftist heap):

  • 每个节点维护一个距离字段(零路径长,到最近的缺失子节点的距离);
  • 不变式:左子树的距离不小于右子树的距离(左偏);
  • 合并:沿两棵树的右路径递归下降,把关键字较小的根作为结果根,其右子树与另一棵树继续合并,若违反左偏则交换左右子树。由于右路径长度受距离字段约束为 O(log n),合并代价 O(log n);
  • 由合并直接得到插入(与单节点堆合并)O(log n) 与删除最值(合并其左右子树)O(log n)。

斜堆(skew heap):

  • 去掉距离字段,每次合并无条件交换左右子树;
  • 单次操作最坏可达 O(n),但均摊 O(log n);
  • 相比左偏树省下一个字段与相应的维护逻辑,代价是失去了单次操作的最坏界。

适用面:分治算法中的候选集合合并、需要把多个优先队列反复合并的场景。若合并不是主要操作,链式节点的指针开销与较差的缓存行为使其不如数组堆。

2.5.5 配对堆与斐波那契堆:降低合并与减键的代价

要补的短板:图算法中 decrease-key 的次数可与边数同阶(Dijkstra 中每条边至多触发一次松弛)。二叉堆每次 decrease-key 为 O(log n),因此 Dijkstra 的代价为 O((V+E) log V)。若把 decrease-key 的均摊代价降到 O(1),即可得到 O(E + V log V)。这类堆(配对堆、斐波那契堆、二项堆)的共同手段是把结构约束放松、把整理工作推迟到删除最值时一次性完成,代价是节点改为带指针的链式分配,从连续的数组变成一组树的森林,缓存局部性与单元素内存开销都变差。

配对堆(pairing heap):

操作 代价 做法
merge O(1) 比较两个根,把较差的根挂为较好的根的孩子
insert O(1) 视作与单节点堆合并
peek O(1) 根即最值
deleteMin 均摊 O(log n) 两趟合并:先把被删根的所有孩子两两配对合并,再从右向左逐个合并
decreaseKey 实践中很快(均摊界未完全确定) 把该节点从父的孩子链表中剪下,与根合并

结构是一棵多路树,除堆序外没有任何形状约束,因此剪枝与合并都只需局部指针操作。实现比斐波那契堆简单,实践中的性能通常更好,是许多优先队列库的实际选择。

斐波那契堆(Fibonacci heap):

操作 摊还代价 做法
insert / merge O(1) 把新树直接挂入根链表,不整理
peek O(1) 维护一个指向最小根的指针
decreaseKey O(1) 剪切节点挂到根链表,必要时对父节点做级联剪枝(标记机制)
deleteMin O(log n) 摘掉最小根并把其孩子并入根链表,再按度数合并度数相同的树

理论上界在各类堆中最优,但结构复杂(势能分析、标记与级联剪枝)、常数因子大、访问模式跳跃,实践中通常不如配对堆或 d 叉堆,主要用于理论分析——例如给出 Dijkstra 的最优复杂度界,或用于需要摊销证明的算法分析。

二项堆可作为两者之间的中间形态:结构规整、合并 O(log n),是斐波那契堆"延迟整理 + 标记剪枝"之前的原型。

共同结论:这类变体不改变"取最值"的语义,只重新分配各操作的代价。选择依据是各操作在实际负载中的频次比例,而不是单看某一个操作的理论最优值。

2.6 与应用场景的对应

2.6.1 Top K 与海量数据求最值

问题:n 个元素中取出最大(或最小)的 K 个,n 远大于 K。

方案:维护一个大小为 K 的小顶堆(求最大的 K 个)。遍历数据,新元素比堆顶大则替换堆顶并下沉,否则丢弃。遍历结束后堆内即结果。

  • 方向判别准则:堆顶是候选集合中"最差的那一个",凡是比它更好的元素才有资格进入候选集合。求最大 K 个用小顶堆(堆顶是候选中最小的,最容易被替换),求最小 K 个用大顶堆。方向写反会得到相反的一半结果(3.6 节)。
  • 复杂度:时间 O(n log K),空间 O(K)。

与其他方案的对照:

方案 时间 空间 适用条件
全部排序后取前 K O(n log n) O(n) 数据可一次装入内存,且需要完整顺序
小顶堆维护 K 个 O(n log K) O(K) K 远小于 n;数据流式到达或无法一次装入内存
快速选择(分治划分) 平均 O(n),最坏 O(n²) O(1) 数据在内存中可随机访问,只需要 Top K 的值
哈希聚合后再取 Top K O(n + m log K) O(m) 先按键聚合(词频、访问量),m 为不同键的数量

要点:

  • 排序的代价与 K 无关,堆方案的代价与 K 有关且只保留 K 个元素,因此 n 大、K 小时优势明显;K 接近 n 时两者趋近;
  • 流式数据不能反复扫描,快速选择无法使用,堆方案可以在线维护;
  • 若还需要结果有序,遍历结束后依次 poll 即可(小顶堆弹出顺序为升序)。

2.6.2 多路归并与外部排序

问题:k 个有序序列合并为一条有序序列。典型来源是外部排序的归并阶段——内存中排好的多个有序段需要合并为更大的段。

方案:用一个大小为 k 的小顶堆保存每路当前游标所指的元素。每次取堆顶输出,然后用该路的下一个元素替换堆顶并下沉。

  • 复杂度:O(N log k),N 为总元素数;空间 O(k)(每个输入流只需一个游标与一块读缓冲)。
  • 若改为每轮线性扫描 k 个游标选最小,代价为 O(N·k)。

归并路数 k 的取舍:k 越大则归并趟数越少(内存可容纳 M 个元素时,趟数为 log_k(N/M)),但堆的一次比较成本随 log k 增长,同时需要同时打开 k 个输入流的缓冲。取值由可用内存与磁盘随机读次数共同约束。

相关实现:当 k 很大且固定时,可以用败者树替代堆——它记录每一层的"败者",每次选择只做 log k 次比较,省去了堆结构中的交换动作,是外部排序中常见的优化;其思想与堆一致,都是把"选择最值"的代价压到 O(log k)。

2.6.3 定时任务与时间轮

语义:延迟任务在到期时间之前不可被取出,到期后按到期时间顺序执行。这要求"按到期时间取最小",因此实现通常是以到期时间为键的小顶堆,堆顶即最早到期的任务(延迟队列的语义与实现见 栈与队列 中延迟队列与时间轮一节)。时间轮的槽位设计、多级层级与堆和时间轮在工程中的取舍见 工程中的数据结构。

与普通优先队列相比有两处额外要求:

  1. 取出需要等待。堆顶元素未到期时不能返回,通常用条件变量的定时等待或带超时的 poll 阻塞到最早到期时刻,避免空轮询;
  2. 取消任务需要删除任意元素。标准库堆不支持 O(log n) 的删除,实现上只能选择惰性删除(标记取消,到期取出时丢弃)或索引堆。

堆方案的瓶颈:任务数量很大且到期时间分散时,每次插入与删除的 O(log n) 成为开销来源。

时间轮(timing wheel) 用另一种结构分摊这一代价:固定长度的环形数组,每个槽位代表一个时间刻度,槽内挂任务链表;插入按到期时间取模定位到槽位,代价 O(1);一个指针按固定 tick 推进,走到某槽位时执行其中的到期任务。

维度 基于堆 基于时间轮
时间精度 不受限,由到期时间直接决定 受 tick 粒度限制,非整数倍需向上取整
插入/删除 O(log n) O(1)
长延时任务 无额外成本 需要多圈或分层时间轮覆盖
适用 任务量中等、延时任意、精度要求高 任务量极大、延时相对集中、可接受 tick 粒度

两者可以组合:分层时间轮承担近期任务,超出轮覆盖范围的长延时任务挂在堆中,到期后再逐级降入下层轮。

2.6.4 任务调度与优先级队列

线程池的优先级执行:把工作队列替换为基于堆的阻塞优先队列,即可按任务优先级而非提交顺序执行。此时要求元素可比较,并且要接受同优先级任务顺序不确定这一事实(并发消费者进一步引入竞争顺序)。

操作系统的调度:就绪队列要按优先级取最小,同时还需要"定位并删除任意任务"(任务被唤醒、优先级调整、超时移除)。Linux 的 CFS 因此用红黑树按虚拟运行时间组织就绪进程,而不是用堆——这一选择与索引堆的动机相同:只要存在"定位任意元素并调整"的需求,堆就必须配反向索引,否则有序结构更直接。调度目标、调度策略与 nice 到优先级的映射见 Linux 进程管理 中进程调度一节。

优先级反转:基于优先级的调度会遇到低优先级任务持有高优先级任务所需资源的情况,处置手段(优先级继承、优先级天花板)属于并发设计的范畴,相关机制见 Java 并发编程。

优先级的边界:优先级队列决定谁先执行,但不阻止低优先级任务长期得不到执行,因此调度策略中另需老化、时间片、多级反馈等机制配合。

2.6.5 图算法中的优先队列

Dijkstra 与 Prim 的主循环都是"从未确定的顶点集合中取关键字最小的一个",正是优先队列的语义。两种算法的正确性依据(非负边权与割性质)、复杂度对照与实现要点见 最短路径与最小生成树。

实现 每次取最小 总代价 备注
线性扫描 O(V) O(V²) 稠密图且 V 较小时常数小,实际未必更慢
二叉堆 O(log V) O((V+E) log V) decrease-key 需索引堆,否则用懒删除
配对堆 / 斐波那契堆 均摊 O(log V) 与 O(1) 的减键 O(E + V log V) 稠密图上收益明显

懒删除(lazy deletion):标准库不提供 decrease-key 时的常用替代。不修改堆中的旧记录,而是插入一条更优的新记录;取出时校验该顶点是否已确定,已确定则丢弃并继续取下一个。代价是堆中元素数可达 O(E)(空间与操作次数上升),实现简单且不需要反向索引。

量级不等于实际速度:O(V²) 的线性扫描在 V 较小(数百以内)且图为稠密时,因缓存友好与无结构调整,实测常快于堆实现。这一现象与"小规模下插入排序胜过归并排序"同源,见 复杂度与算法分析 中理论与实测的差异一节。

2.6.6 流式计算中的滑动窗口最值

问题:数据流中维护固定大小窗口的最大值(最小值同理)。

堆方案:把窗口内的元素放入大顶堆,堆顶即最大值;窗口右移时插入新元素,滑出左边界的元素用惰性删除处理——堆中保存 (值, 位置),取出堆顶时若位置已过期则丢弃。单次操作 O(log w),总量 O(n log w),且堆中可能堆积过期元素,空间最坏可达 O(n)。

单调队列方案:队列内元素保持单调递减,队首即窗口最大值;过期元素从队首直接弹出,每个元素至多入队一次、出队一次,总代价 O(n)、空间 O(w)。

结论:窗口滑动时元素的过期顺序与入队顺序一致,这一额外信息使单调队列能同时完成"取最值"与"淘汰过期",优于堆方案;堆方案适用于过期顺序不可利用(窗口边界任意、需要按位置删除)的情形。单调队列的实现与复杂度对照见 栈与队列 中单调队列一节。

若窗口问询涉及任意区间(不只是固定长度的滑动窗口),则超出这两种结构的范围,属于区间查询结构的话题。


三、实现

3.1 二叉堆实现要点

3.1.1 存储与字段

  • 数组与逻辑大小分离。用 Object[] items 与 int size 表示堆,size 而非 items.length 才是堆的边界。删除元素只需减小 size,不必分配新数组。
  • 扩容。容量不足时按倍数扩容并复制,与动态数组的摊还结论一致;扩容瞬间旧数组与新数组同时存在,峰值内存达到新容量的 1.5 倍,这一点对元素量大的优先队列同样成立,扩容峰值的来源与预估方式见 Java 集合框架实现原理。
  • 比较器。统一用 Comparator<? super E> 表达顺序,不在结构内部假设自然序;未传比较器而元素未实现 Comparable 时,异常发生在第一次比较时(插入或取堆顶),不在构造时。
  • 释放引用。出队后把数组尾部槽位置为 null,避免长期持有已出队元素(元素为大对象时表现为内存不下降)。

3.1.2 上浮与下沉的代码结构

  • 两者都用循环实现,不用递归:递归下沉会引入 O(log n) 的调用栈,也更容易在边界上写错。
  • 下沉时"选两个孩子中最优先者"的顺序:先假定左孩子最优,再在右孩子存在且更优先时更新,避免写两个分支比较三次。
  • 采用空穴法减少赋值:暂存待下移的值,沿途把更优子节点上提,最后把值落到空位。相比三赋值交换,每层从 3 次写入降为 1 次。

3.1.3 比较器与相等元素

  • 比较器必须满足契约(自反、反对称、传递)。不满足传递性时,堆序可能局部不成立且难以复现,症状是"取出顺序不符合预期"。
  • 相等关键字可以出现在任意位置,堆不保证相等元素的相对顺序。需要稳定语义时,在比较器中追加次序键(例如插入序号)。
  • 比较器应当是纯函数:在其中修改元素状态会造成"比较结果依赖调用次数"的不确定行为。

3.1.4 边界与越界

  • 空堆 peek() / poll() 的行为需要明确约定:返回 null 还是抛异常。Java 的 PriorityQueue.poll 返回 null,element/remove 抛 NoSuchElementException;两种口径都可用,混用会导致空指针。
  • 禁止插入 null:null 无法参与比较,且 null 返回值本身要用于表示空堆。
  • 下沉中孩子下标越界必须分两级判断:先判断 left < size,再判断 right < size。
  • 单元素堆的下沉不应访问任何孩子;poll 在删除最后一个元素后不应再执行下沉。
  • 上浮终止条件为"到达根"或"父节点已满足堆序",下沉终止条件为"到达叶子"或"已满足堆序",两者都必须写全。

3.1.5 完整实现

import java.util.Comparator;

/** 小顶堆;传入 Comparator.reverseOrder() 即为大顶堆语义。 */
public class BinaryHeap<E> {

    private Object[] items;
    private int size;
    private final Comparator<? super E> cmp;

    public BinaryHeap(int initialCapacity, Comparator<? super E> cmp) {
        this.items = new Object[Math.max(1, initialCapacity)];
        this.cmp = cmp;
    }

    public void offer(E e) {
        if (e == null) {
            throw new NullPointerException("null element is not comparable");
        }
        if (size == items.length) {
            grow();
        }
        items[size] = e;
        siftUp(size++);
    }

    @SuppressWarnings("unchecked")
    public E peek() {
        return size == 0 ? null : (E) items[0];
    }

    @SuppressWarnings("unchecked")
    public E poll() {
        if (size == 0) {
            return null;
        }
        E top = (E) items[0];
        int last = --size;                       // 逻辑大小先减一,末尾元素退出堆
        E moved = (E) items[last];
        items[last] = null;                      // 释放引用
        if (size > 0) {
            items[0] = moved;                    // 末尾元素补充到堆顶
            siftDown(0);
        }
        return top;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /** 上浮:与唯一的父节点比较,最多上升树高。空穴法实现。 */
    @SuppressWarnings("unchecked")
    private void siftUp(int i) {
        E e = (E) items[i];
        while (i > 0) {
            int parent = (i - 1) >>> 1;          // 无符号右移等价于整除 2
            E p = (E) items[parent];
            if (cmp.compare(e, p) >= 0) {
                break;                           // 已满足堆序
            }
            items[i] = p;                        // 父节点下移,空穴上浮
            i = parent;
        }
        items[i] = e;
    }

    /** 下沉:与两个孩子中最优先者比较,最多下降树高。空穴法实现。 */
    @SuppressWarnings("unchecked")
    private void siftDown(int i) {
        E e = (E) items[i];
        int half = size >>> 1;                   // i >= half 时为叶子,无需下沉
        while (i < half) {
            int child = 2 * i + 1;
            int right = child + 1;
            if (right < size && cmp.compare((E) items[right], (E) items[child]) < 0) {
                child = right;                   // 取两个孩子中更优先的一个
            }
            if (cmp.compare(e, (E) items[child]) <= 0) {
                break;
            }
            items[i] = items[child];             // 孩子上提,空穴下移
            i = child;
        }
        items[i] = e;
    }

    private void grow() {
        Object[] bigger = new Object[items.length * 2];
        System.arraycopy(items, 0, bigger, 0, size);
        items = bigger;
    }
}

要点核对:

  • siftUp 的 (i - 1) >>> 1 与 siftDown 的 2 * i + 1 是 2.2.2 节的下标公式;
  • half = size >>> 1 即"第一个叶子节点的下标",用它作为下沉的循环上界,省去每次查找孩子后判空;
  • 两个孩子中"更优先者"由比较器的方向决定,因此同一份代码在传入反向比较器后即为大顶堆;
  • 若需要在线插入后直接建堆,构造函数可以从数组初始化并调用一次自底向下沉的循环,代价 O(n)。

3.1.6 语言内置实现的使用要点

语言 类型 堆方向 线程安全 使用限制
Java PriorityQueue 小顶堆(传 Comparator.reverseOrder() 得大顶堆) 否 不允许 null;迭代顺序不保证;remove(Object) 为 O(n);无 decrease-key
Java PriorityBlockingQueue 小顶堆 是(阻塞) 无界(构造函数容量仅为初始值,会扩容);take 阻塞而 put 不阻塞
Java DelayQueue 按到期时间 是(阻塞) 元素必须实现 Delayed;remove(Object) 为 O(n)
Python heapq 小顶堆 否 以函数操作普通 list;无 decrease-key;大顶堆需存负值;元素为元组时后续字段必须可比较
C++ std::priority_queue 大顶堆(传 greater<T> 得小顶堆) 否 不提供迭代器与遍历;不支持删除任意元素
Go container/heap 由 Less 决定 否 需实现 Len/Less/Swap/Push/Pop 五个方法

三个共性问题:

  1. 迭代顺序不是出队顺序。堆只保证堆顶为最值,需要有序序列时必须连续 poll。各容器的迭代顺序与复杂度对照见 Java 集合框架实现原理 中集合选型的复杂度总表。
  2. 不提供 decrease-key。修改优先级的通用做法是 remove 后重新 offer(O(n) 定位)或改用索引堆(3.2 节)。
  3. 相等元素顺序不保证。需要稳定语义时在比较器中加入次序键。

3.2 索引堆实现要点

3.2.1 结构与不变式

索引堆用三个数组把"外部下标"与"堆中位置"解耦:data 按下标存键,heap[p] 表示堆中第 p 个位置放的是哪个下标,pos[i] 表示下标 i 当前在堆中的位置。两条互为逆映射的不变式必须同时成立:heap[pos[i]] == i 且 pos[heap[p]] == p。

3.2.2 交换必须同步更新反向索引

交换堆中位置 p 与 q:
    heap[p] ↔ heap[q]
    pos[heap[p]] 与 pos[heap[q]] 随之互换        ← 漏掉这一步,定位即失效

上浮与下沉都由多次交换构成,因此把交换封装成单个方法,是保证两条映射同步的可行做法。

3.2.3 修改与删除任意元素的流程

  • 修改:写 data[i],与修改前的值比较——变小只需上浮,变大只需下沉,两个方向不会同时违反堆序。
  • 删除:用堆末尾元素填补待删位置,然后判断该位置与父节点是否冲突——冲突则上浮,否则下沉,两者只执行其一。
  • 无反向索引时的删除:线性定位 O(n) 后删除;或者先改到极端值再 deleteMin(两次调整的代价);或者标记删除、取出时跳过(惰性删除)。批量删除后一次性重建堆 O(n) 通常更划算。

3.2.4 完整实现

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 索引小顶堆:外部下标 i 对应一个键,支持 O(log n) 的修改与删除任意元素。
 * pos[i] == -1 表示下标 i 当前不在堆中。
 */
public class IndexedMinHeap {

    private final double[] keys;     // 外部下标 -> 键
    private final int[] heap;        // 堆位置 -> 外部下标
    private final int[] pos;         // 外部下标 -> 堆位置
    private int size;

    public IndexedMinHeap(int capacity) {
        this.keys = new double[capacity];
        this.heap = new int[capacity];
        this.pos = new int[capacity];
        Arrays.fill(pos, -1);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(int i) {
        return pos[i] != -1;
    }

    public int peekIndex() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty");
        }
        return heap[0];
    }

    public double keyOf(int i) {
        return keys[i];
    }

    public void insert(int i, double key) {
        if (contains(i)) {
            throw new IllegalStateException("already in heap: " + i);
        }
        keys[i] = key;
        heap[size] = i;
        pos[i] = size;
        siftUp(size++);
    }

    /** 修改下标 i 的键;方向由键的增减决定,只需一个方向的调整。 */
    public void change(int i, double key) {
        if (!contains(i)) {
            throw new IllegalStateException("not in heap: " + i);
        }
        double old = keys[i];
        keys[i] = key;
        if (key < old) {
            siftUp(pos[i]);
        } else if (key > old) {
            siftDown(pos[i]);
        }
    }

    public int deleteMin() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty");
        }
        int min = heap[0];
        int last = heap[--size];
        heap[size] = -1;
        pos[min] = -1;
        if (size > 0) {
            heap[0] = last;
            pos[last] = 0;
            siftDown(0);
        }
        return min;
    }

    /** 删除下标 i 处的元素;用堆末尾元素填补后只做一个方向的调整。 */
    public void remove(int i) {
        int p = pos[i];
        if (p == -1) {
            throw new IllegalStateException("not in heap: " + i);
        }
        int last = heap[--size];
        heap[size] = -1;
        pos[i] = -1;
        if (p != size) {                      // 被删元素原本不在末尾,需要填补空位
            heap[p] = last;
            pos[last] = p;
            int parent = (p - 1) >>> 1;
            if (p > 0 && keys[last] < keys[heap[parent]]) {
                siftUp(p);                    // 与父节点冲突
            } else {
                siftDown(p);                  // 否则只可能与子节点冲突
            }
        }
    }

    private void swap(int p, int q) {
        int a = heap[p];
        int b = heap[q];
        heap[p] = b;
        heap[q] = a;
        pos[a] = q;
        pos[b] = p;                           // 两条映射必须同步
    }

    private void siftUp(int p) {
        while (p > 0) {
            int parent = (p - 1) >>> 1;
            if (keys[heap[p]] >= keys[heap[parent]]) {
                break;
            }
            swap(p, parent);
            p = parent;
        }
    }

    private void siftDown(int p) {
        int half = size >>> 1;
        while (p < half) {
            int child = 2 * p + 1;
            int right = child + 1;
            if (right < size && keys[heap[right]] < keys[heap[child]]) {
                child = right;
            }
            if (keys[heap[child]] >= keys[heap[p]]) {
                break;
            }
            swap(p, child);
            p = child;
        }
    }
}

要点核对:

  • insert 在 pos[i] 有效时拒绝重复插入,否则同一下标会在堆中出现两次,pos 只能记录其中一个位置;
  • remove 中"先判断与父节点是否冲突"是必要的:与父不冲突时只可能与子冲突,两个方向不会同时不成立;
  • deleteMin 与 remove 都必须处理"被移动的末尾元素就是被删元素本身"这一情形(此时无需调整),否则会多一次无意义的调整或读到已失效的槽位;
  • peekIndex 返回外部下标,调用方通过 keyOf 读取键,避免外部直接持有可能被覆盖的堆内位置;
  • 三个数组按构造时的容量分配,不自动扩容。索引堆的外部下标通常是范围有限的标识(顶点编号、任务编号),容量可预估是其常见前提;若下标范围不可控,需要额外维护下标到槽位的映射。

3.3 应用代码

3.3.1 Top K:小顶堆维持 K 个元素

import java.util.PriorityQueue;

/** 返回数组中最大的 k 个元素(升序)。时间复杂度 O(n log k),空间 O(k)。 */
public static int[] topK(int[] nums, int k) {
    if (nums == null || k <= 0) {
        return new int[0];
    }
    int limit = Math.min(k, nums.length);
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(limit);   // 小顶堆:堆顶是候选中最小的
    for (int x : nums) {
        if (minHeap.size() < limit) {
            minHeap.offer(x);
        } else if (x > minHeap.peek()) {                           // 比候选中最差的更好
            minHeap.poll();
            minHeap.offer(x);
        }
    }
    int[] result = new int[minHeap.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = minHeap.poll();                                // 依次弹出得到升序
    }
    return result;
}

要点:

  • 求最大 K 个用小顶堆,求最小 K 个用大顶堆,方向一旦写反,结果恰好是"最小的 K 个"(3.6 节);
  • limit 必须与 nums.length 取小,否则 k > n 时输出长度与堆内元素数不一致;
  • 替换动作必须是"先 poll 再 offer"或直接用 PriorityQueue 之外的实现做一次 replace,中间不能出现"元素同时存在于堆内外"的假设;
  • 若输入是数据流,把该循环放到消费端,堆作为成员变量长期持有即可,空间始终为 O(K)。

3.3.2 中位数维护:双堆

import java.util.Comparator;
import java.util.PriorityQueue;

/** 数据流中位数:大顶堆存较小的一半,小顶堆存较大的一半。 */
public class MedianFinder {

    private final PriorityQueue<Integer> low =
            new PriorityQueue<>(Comparator.reverseOrder());   // 大顶堆,堆顶为较小一半的最大值
    private final PriorityQueue<Integer> high =
            new PriorityQueue<>();                            // 小顶堆,堆顶为较大一半的最小值

    public void add(int x) {
        low.offer(x);
        high.offer(low.poll());         // 经 low 中转,保证 low 的最大值不大于 high 的最小值
        if (high.size() > low.size()) {
            low.offer(high.poll());     // 维持大小差不超过 1,且 low 不短于 high
        }
    }

    public double median() {
        if (low.isEmpty()) {
            throw new IllegalStateException("no data");
        }
        if (low.size() > high.size()) {
            return low.peek();
        }
        return (low.peek() + high.peek()) / 2.0;   // 接近整型上限时需先用 long 或 double 中转
    }
}

要点:

  • 先入 low 再搬运是中转写法的核心:直接比较两个堆顶再决定入哪一侧,会让相等元素的分支判断变得不可预期;
  • 两条不变式分别对应"跨堆顺序"与"数量差",缺一不可;
  • 插入 O(log n),取中位数 O(1);若每次插入后重新排序,单次代价为 O(n log n)。

3.3.3 合并 K 个有序序列:多路归并

import java.util.Comparator;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

/** 合并 k 条升序链表;时间 O(N log k),空间 O(k),N 为节点总数。 */
public static ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists) {
        if (head != null) {
            heap.offer(head);
        }
    }
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        tail.next = node;                      // 摘下的节点直接接到结果链表尾部
        tail = node;
        if (node.next != null) {
            heap.offer(node.next);             // 同一路的下一节点替换堆顶
        }
    }
    return dummy.next;
}

要点:

  • 堆中最多同时存在 k 个节点,空间与总数据量无关;
  • 每路各自有序是算法的前提,堆只负责在 k 个游标中选择最小;
  • 若 k 路都是有序文件,把节点换成 (当前值, 文件句柄) 即可用于外部归并;
  • Python 的 heapq.merge 直接提供同一能力,heapq.nlargest / nsmallest 内部用堆实现 Top K。

3.3.4 任务调度:优先级与稳定性

import heapq
import itertools


class PriorityScheduler:
    """按优先级调度任务;相同优先级按提交顺序执行(用递增序号作为次序键)。"""

    def __init__(self):
        self._heap = []
        self._counter = itertools.count()
        self._cancelled = set()

    def submit(self, priority, task):
        # priority 越小越先执行;序号既是稳定的次序键,也避免 task 不可比较时报错
        heapq.heappush(self._heap, (priority, next(self._counter), task))

    def run_next(self):
        while self._heap:
            _, _, task = heapq.heappop(self._heap)
            if task not in self._cancelled:      # 惰性删除:取出时才丢弃已取消的任务
                return task
        return None

    def cancel(self, task):
        """取消任务:heapq 不支持按键删除,先标记,取出时跳过(惰性删除)。"""
        self._cancelled.add(task)                # 已取消元素仍占堆内空间,需要时可批量重建

要点:

  • heapq 只实现小顶堆;需要"数值越大越先执行"时对优先级取负,或反转比较键;
  • 二元组 (priority, task) 在优先级相同时会比较 task,若任务对象不可比较则抛 TypeError,因此必须加入可比较的次序键;
  • 标准库不提供 decrease-key:修改已入队任务的优先级需要 remove 后重新入队(列表实现为 O(n)),或改用索引堆(3.2 节);如果这样的修改频繁,索引堆是更合适的选择。

3.4 复杂度与实测

3.4.1 各操作复杂度表

操作 二叉堆 d 叉堆(d = 4) 平衡二叉搜索树 斐波那契堆
peek O(1) O(1) O(log n) O(1)
insert O(log n) O(log_d n) O(log n) 均摊 O(1)
deleteMin O(log n) O(d · log_d n) O(log n) 均摊 O(log n)
decreaseKey O(log n)(需反向索引) O(log_d n)(需反向索引) O(log n) 均摊 O(1)
merge O(n1 + n2) O(n1 + n2) O(n1 + n2)(逐个插入) O(1)
建堆 O(n) O(n) O(n log n) O(n)
查找任意元素 O(n) O(n) O(log n) O(n)
有序遍历 O(n log n)(反复取堆顶) 同左 O(n)(中序) 同左

3.4.2 实测的注意点

  1. 建堆与逐个插入的差异在小规模上被常数掩盖。两者量级不同(O(n) 与 O(n log n)),差距随 n 增大而扩大;基准需要按 n 分档(例如 10³、10⁴、10⁵、10⁶)测量并观察比值的变化趋势,只看单一规模的绝对值无法区分"常数差异"与"量级差异"。
  2. 手写计时在 JIT 环境下不可靠。预热不足、死代码消除、常量折叠都会使结果偏离真实值,比较两种建堆方式或堆与排序的差异必须使用基准框架,相关陷阱与结果判读方式见 JMH 微基准测试。
  3. 缓存效应会改变实现之间的排序。堆的下沉访问跨越数组的不同层,链式实现的指针追逐更差;数组连续存储带来的局部性收益见 数组与链表,量级相同而实测不同的原因分析见 复杂度与算法分析 中理论与实测的差异一节。
  4. Top K 的对比要控制三个变量:是否真的需要完整顺序(只需要 Top K 时全排序有大量无效工作)、K 与 n 的比例(K 接近 n 时堆方案趋近全排序)、数据是否可重复访问(流式数据无法使用快速选择)。基准应至少覆盖 K 很小(如 10)与 K 居中(如 n/2)两类用例。
  5. 比较器的成本常被忽略。若比较器内部做字符串拼接、正则或字段解析,单次操作的实际开销由比较器主导而非堆操作主导;把键预先提取(pack 成数值或缓存字段)往往比更换结构更有效。
  6. 结果表述口径。基准给出的是带误差范围的均值,判断两个实现是否更快应看差异是否超出误差范围,而不是比较小数点后的数值。

3.5 工程应用

3.5.1 语言内置优先队列的使用要点与限制

内置实现的共同限制集中在"堆只保证堆顶"这一事实上:

  • 不保证迭代有序:迭代或打印优先队列得到的顺序不是出队顺序;需要有序序列时连续 poll;
  • 不提供 decrease-key:修改优先级需要 remove 后重新 offer(O(n) 定位)或使用索引堆;
  • remove(Object) 是 O(n):Java 的实现用 equals 线性扫描后删除,频繁删除任意元素时应重新评估结构选择;
  • 不接受 null:元素必须可比较,且 null 返回值需表示空堆;
  • 初始容量会影响扩容次数:元素数可预估时在构造时给出容量,避免扩容峰值(Java 集合框架实现原理)。

3.5.2 并发场景下的阻塞优先队列

实现 语义 限制
PriorityBlockingQueue 堆操作加锁,take 在空时阻塞 无界:容量参数只是初始值,put 不阻塞,无法提供背压,积压表现为堆内存增长
DelayQueue 按到期时间排序的堆,take 等待到最早元素到期 元素必须实现 Delayed;删除任意元素为 O(n)

并发设计上的要点(锁的粒度、条件变量的循环判断、无界队列的风险、拒绝策略)见 Java 并发编程 中线程池与工作队列相关各节;集合的线程安全口径与弱一致迭代见 Java 集合框架实现原理 中与并发的配合一节。

需要"按优先级执行"的线程池把工作队列替换为优先阻塞队列即可,但要接受两点:入队元素必须可比较;多个消费者并发取出时,同优先级任务的执行顺序更不可预期。

3.5.3 操作系统调度中的优先级与有序结构

  • CFS 用红黑树按虚拟运行时间组织就绪进程,取最左节点即最小者。选择树而非堆的原因是调度器还需要定位并删除单个任务、修改其虚拟运行时间,这些操作在堆上需要反向索引才能保持对数代价(Linux 进程管理 中进程调度一节)。
  • 实时调度策略(SCHED_FIFO / SCHED_RR)按优先级抢占、同级轮转,其"优先级"是固定分级,不需要堆维护动态关键字。
  • 内核的定时与延迟工作同样需要"按到期时间取最小",与用户态延迟队列同构,结构选择见 2.6.3 节。
  • 对照用户态:任务调度器的结构选择依据相同——取消必须立即生效且要释放内存时,索引堆或有序结构更合适;取消可以惰性处理时,普通堆足够。

3.5.4 延迟任务的实现选择

场景 倾向的结构 理由
任务量中等、延时任意、精度要求高 以到期时间为键的堆(延迟队列) 精度不受 tick 限制,逻辑简单
任务量极大、延时集中、可接受 tick 粒度 时间轮 插入 O(1),避免 O(log n) 成为瓶颈
需要跨进程共享或持久化 外部存储(如 Redis 有序集合按到期时间轮询取出) 进程重启不丢任务;但无确认与重试语义

时间轮与堆的取舍、分级时间轮的组合方式见 栈与队列 中延迟队列与时间轮一节;外部实现的原子性、失败降级与确认语义的差异见 Redis 缓存实践 中延时队列与轻量任务调度一节。

3.5.5 内存约束:Top K 与大对象

堆方案的常驻内存与 K 成正比,这一点容易被忽略:K 由业务决定(榜单取前 1000、Top 100 等),但元素本身的体积常是"整条记录"或"长文本",K 个元素加上引用开销可占数百 MB,并且在被替换之前一直持有引用。

处理方向:

  • 只把排序所需的部分放进堆:堆内保存 (排序键, 定位标识),原始数据留在外部存储中,需要结果时再按标识取回;
  • 先聚合再取 Top K:用哈希或流式聚合把候选集压缩到 m 个键,再从 m 个键中取 K 个,代价 O(n + m log K) 而常驻集只有 m 与 K;
  • 给 K 设上界:把 K 作为配置项,在入口校验,避免外部输入直接决定内存占用。

诊断方向:堆内存持续增长时,先确认是否存在无界优先队列或过大的 K,再用类直方图与堆转储定位持有链;诊断动作自身的代价、转储的停顿与顺序见 应用诊断与调优 中剖析与转储一节,堆内与堆外占用的区分与该文内存类问题的判断口径一致,JVM 堆的结构与垃圾回收机制见 JVM 内存结构与垃圾回收。

3.6 常见问题与排查

现象 可能原因 验证与处置
Top K 结果恰好是相反的一半(要最大却拿到最小) 堆方向与目标相反:求最大 K 个应使用小顶堆,求最小 K 个应使用大顶堆 检查替换条件与比较器方向是否一致(求最大 K 个的条件是"新元素 > 堆顶");用 n = 5、k = 2 的小输入手工推演一遍
修改元素优先级后,取出的不再是真正的最值 元素对象的关键字被就地修改,堆序被破坏且无任何报错;或修改后未重新上浮/下沉 把参与比较的字段设为不可变;所有修改走统一入口(索引堆的 change,或 remove 后重新 offer);用"连续 poll 的结果是否有序"验证堆序
优先队列占用内存持续增长 阻塞优先队列无界(容量参数只是初始值);K 取值过大;元素为大对象;惰性删除留下大量过期元素 打印队列长度随时间的变化并与元素体积相乘估算占用;改为有界队列并配置拒绝或降级策略;对过期元素定期批量重建(自底向下沉 O(n));确认诊断口径与持有链(应用诊断与调优)
相同优先级的任务执行顺序每次都不同 堆不保证相等元素的相对顺序;并发消费者进一步引入竞争 需要稳定语义时在比较器中加入递增序号作为次序键;不要在文档或测试中依赖同优先级的顺序
取出顺序与预期不符,遍历优先队列发现是无序的 误把优先队列当作有序容器 需要有序序列时连续 poll;不要在迭代中做"顺序相关"的判断
抛 IllegalArgumentException: Comparison method violates its general contract 比较器不满足传递性,例如用两数相减实现整数比较(溢出导致符号错)或对浮点做不一致的判断;该异常由排序(TimSort)抛出,堆可能不抛异常但顺序错乱 用 Integer.compare / Double.compare 替代相减;保证比较器是纯函数,不在其中修改元素状态
抛 ClassCastException: cannot be cast to Comparable 元素未实现 Comparable 且构造优先队列时未传比较器 初始化时传入明确的比较器;检查泛型擦除后元素的实际类型是否混杂
抛 NullPointerException,位置在入队或比较处 插入了 null,堆元素必须可比较 入队前显式校验;把"元素可能为空"的场景改为包装类型或哨兵值
大量入队出队的接口延迟上升 单次 O(log n) 的调整叠加缓存未命中;元素数增大使 log n 上升;比较器本身开销大(字符串解析、字段拼接) 用基准分别测量"堆操作时间"与"比较器时间",确认瓶颈归属;把键预先提取并缓存;批量场景改用 O(n) 建堆;插入密集且删除少时考虑 d 叉堆
定时任务触发时刻早于或晚于预期 到期时间使用相对时间而非绝对时间戳,或单位、时区不一致;时间轮的 tick 粒度向上取整 统一用绝对时间戳与同一时钟源;核对 tick 与最大延时覆盖范围;用条件变量的定时等待而非空轮询
图算法结果正确但耗时随边数急剧上升 采用懒删除导致堆中元素达到 O(E);或在应执行 decrease-key 的场景反复插入 记录堆中元素的峰值并与 V、E 对照;评估是否改用索引堆或配对堆;小规模稠密图上线性扫描可能更快,需实测判断

排查这类问题的通用手段有两类证据:

  1. 结构状态:堆的逻辑大小、堆顶元素、队列长度、过期元素数量、比较器被调用的次数。堆的缺陷大多表现为"不变式被破坏",而这些量能把不变式的变化暴露出来;
  2. 不变式自检:对堆数组做一次线性扫描,验证每个节点与其子节点满足堆序(O(n));索引堆额外验证 heap[pos[i]] == i;对 Top K 验证"堆内元素两两之间与外部元素的大小关系是否符合预期"。这类自检的代价是线性的,可以在测试与预发环境常态开启。

3.7 检查清单

堆的实现与使用可以按以下条目自检:

  • 堆的边界用逻辑大小还是数组长度判定;删除元素后尾槽是否置空。
  • 下沉时是否与两个孩子中更优先者比较;右孩子是否存在是否单独判断;叶子节点是否提前退出。
  • 上浮与下沉的终止条件是否同时覆盖"到达边界"与"堆序已满足"两种情况。
  • 是否禁止插入 null;空堆 peek / poll 的返回值是否有明确约定,调用方是否区分了"空堆"与"元素值恰好为 null"。
  • 比较器是否满足传递性;是否用 compare 而非相减;是否在其中修改了元素状态。
  • 需要稳定语义时,比较器是否包含次序键。
  • 是否存在"修改已入队元素优先级"的路径;是否统一走 change / remove 后重新 offer,而不是直接改对象字段。
  • 是否存在"删除任意元素"的需求;remove(Object) 的 O(n) 是否可接受;频繁使用时是否应改为索引堆或惰性删除加定期重建。
  • 索引堆中 heap 与 pos 的两条映射是否在每次交换后都成立;删除时是否处理了"被移动元素即被删元素"的情形。
  • 数据流场景中堆的方向与替换条件是否与目标一致;K 是否设置了上界。
  • 队列是否有容量上限与背压策略;无界优先队列的积压是否有监控指标。
  • 常驻内存是否按"K × 单元素大小"估算过;是否可以把原始数据留在外部存储。
  • 延迟任务是否明确选择了堆或时间轮,以及到期时间的时钟源与精度口径。
  • 性能结论是否来自基准框架,并区分了预热与测量阶段、记录了元素规模与 K 的取值。

四、总结

堆与优先队列的关系可以概括为:优先队列规定"每次取出当前最优的元素",堆用最弱的有序性承诺实现这一语义。它只要求"堆顶是最值"与"父子之间满足偏序",放弃了对兄弟、子树以及任意元素之间关系的一切承诺,换来了取最值 O(1)、插入与删除最值 O(log n) 的代价,以及"查找任意元素与有序遍历退回 O(n)"这一必须接受的限制。

原理层面的主线:

  • 部分有序是代价与能力的交换点。完全有序确定了任意两个元素的先后,代价是全局维护;堆只维护从根到叶的偏序,把每次修改的影响限制在一条长度为 O(log n) 的路径上。后续所有变体都在重新划分这一交换的位置。
  • 完全二叉树与数组互相成就。完全性保证层序编号连续无空洞,使数组下标与树节点一一对应;数组使父子定位变成算术运算,并使同一层的节点在内存中相邻。放弃完全性(可合并堆)或增加反向索引(索引堆)都会改变这一组合的代价结构。
  • 上浮与下沉是所有操作的原子动作。插入是"追加 + 上浮",删除最值是"末尾上位 + 下沉",修改是"改键 + 单向调整",建堆是"全部元素 + 自底向下沉",堆排序是"建堆 + 反复取堆顶"。理解这两个动作的终止条件与比较对象,就掌握了堆的全部实现细节。
  • 建堆的 O(n) 来自级数收敛。高层节点数量按 1/2^h 递减而代价按 h 线性增长,求和收敛;底层节点占多数且代价为零。这一结论与动态数组扩容、路径压缩的摊还分析同源。
  • 变体对应具体短板:索引堆补定位(change / remove 变 O(log n))、双堆补"中间量"查询(中位数 O(1))、d 叉堆在插入与删除之间调比例、左偏树与斜堆补合并(O(log n))、配对堆与斐波那契堆把 decrease-key 摊薄到 O(1) 以改善图算法的界。选择依据是各操作的实际频次比例与额外需求,而不是某一操作的理论最优值。
  • 场景决定结构:Top K 用"大小为 K 的反向堆"、多路归并用"大小为 k 的小顶堆"、定时任务用"以到期时间为键的堆或时间轮"、图算法用"支持减键或懒删除的堆"、滑动窗口最值用"利用过期顺序的单调队列"。每个场景的选择都能由"需要哪种有序性、需要哪些额外操作"推出。

实现与工程层面需要落到位的几点:

  • 边界与不变式:空堆、单元素、孩子越界、末尾填补、索引堆的双向映射,是缺陷集中出现的四类位置;不变式自检(线性验证堆序与映射)代价低、收益明确。
  • 比较器是堆语义的一部分:方向决定大顶堆还是小顶堆,契约决定堆序是否成立,相等元素的处理决定是否稳定,比较器的成本决定实际性能。
  • 内置实现的能力边界:不保证迭代有序、不提供 decrease-key、remove(Object) 为 O(n)、不接受 null;这些限制都来自"堆只保证堆顶"这一事实,绕过它们需要额外结构(索引堆、惰性删除、定期重建)。
  • 并发语义:阻塞优先队列把等待条件封装进队列,但无界队列无法提供背压,积压只能以内存增长的形式暴露。
  • 有序结构未必更慢:操作系统调度器选择红黑树而非堆,是因为存在"定位并删除任意任务"的需求;这一例子说明结构选择由操作集合决定,而不是由某个操作的复杂度排名决定。

堆的价值在于用最小的有序性承诺换取最值操作的对数代价。理解了"哪些顺序被承诺、哪些没有",以及每类额外需求会给这一承诺增加多少维护成本,堆及其全部变体的取舍都可以在同一个框架下判断。