深夜的急诊室，护士长面前是一块白色登记板。每当救护车送来病人，她不按先来后到，而是根据病情危重程度安排床位：最危险的永远躺在最显眼的 1 号床。新病人来了，先在板尾加一行，再一路“上浮”到合适位置；1 号床的病人出院，就把板尾的病人调过来，再一路“下沉”安顿。这块登记板的魔力在于：床位编号隐藏着严谨的数学结构，不需要任何额外标记就能瞬间算出父子关系，所有操作都只需“对数级”的功夫。这就是堆——一种用完全二叉树实现的优先队列。本文将从这张登记板讲起，带你走遍堆的结构、建堆、排序、变体与实战应用。

岗位关联

堆是 Top-K、任务调度、Dijkstra 最短路径的幕后引擎。掌握它，你就掌握了海量数据里“永远快速找到极值”的核心技能，这是算法面试与系统设计的必备直觉。

目录
  1. 可视化演示
  2. 完全二叉树：急诊室的登记板布局
  3. 堆序性质：最高危优先的分诊
  4. 建堆算法：开诊前的全院排序
  5. 上浮下沉：新病人与出院处理
  6. 堆排序原理：按病情从重到轻出院
  7. 堆变体对比：不同规模的急诊室选型
  8. 典型应用：Top-K 与 Dijkstra
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示堆的完全二叉树与数组表示、插入上浮操作流程、以及堆排序的建堆-交换-下沉完整过程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

堆的树形与数组表示 完全二叉树：父节点i的子节点为2i+1和2i+2 最大堆性质：父节点值大于等于子节点 parent(i) = floor((i-1)/2), left(i) = 2i+1, right(i) = 2i+2 堆是完全二叉树的数组表示满足堆序性质

完全二叉树：急诊室的登记板布局

凌晨急诊室换班，护士长小周在白板上画床位图：1 号床居中，2、3 号床列在下一层，4 到 7 号床再下一层。她告诉新人一条铁律：“上面没住满，多一间都不开；号码按层连，亲属好计算。”住 7 号床的病人，家属要么睡在 3 号床，孩子将来睡 14、15 号床。整个急诊室不需要通讯录，靠编号就能推算所有亲戚关系。

这种“先挤满上层再向下层”的树形床位，就是计算机里的完全二叉树。它的伟大之处在于：不需要指针，一个普通数组就能装下整棵树——数组下标天然就是床位号。堆正是以这种结构为骨架的优先队列：我们用一个整数就能瞬间找到任意结点的父结点与孩子，内存也毫无空洞。

为什么完全二叉树如此重要？因为数组紧凑，下标换算才成立；而下标换算是堆一切操作的地基。后续的上浮、下沉、建堆，本质都是在做“顺着下标走亲戚”的路径搜索，路径长度等于树高。

小周把这张床位图挂在墙上，新人只需按公式心算，就能在密密麻麻的登记板里准确找到任何病人的“亲属床位”。堆之所以能又快又省地运行，正是因为这个看似简单的数学结构。

parent(i)=⌊i−12⌋,left(i)=2i+1,right(i)=2i+2\text{parent}(i)=\left\lfloor \displaystyle\frac{i-1}{2}\right\rfloor,\qquad \text{left}(i)=2i+1,\qquad \text{right}(i)=2i+2
这三个公式是堆的“寻亲公式”：给任意床位号，立刻算出父床位与两个子床位。
  1. 父节点下标将下标减 1 后除以 2 再向下取整，就能倒推任意结点的父结点；这是数组表示中“往回走”的唯一钥匙。
    parent(i)=⌊i−12⌋\text{parent}(i)=\left\lfloor \displaystyle\frac{i-1}{2}\right\rfloor
  2. 左孩子下标任意结点乘 2 再加 1，得到左孩子的位置；因为完全二叉树逐层填满，左孩子必然紧随其后。
    left(i)=2i+1\text{left}(i)=2i+1
  3. 右孩子下标左孩子加 1 即右孩子，两个孩子相邻存储，数组的连续性让查寻零成本。
    right(i)=2i+2\text{right}(i)=2i+2
  4. 使用前提下标从 0 开始计数，且堆始终是“无空洞”的完全二叉树，公式才成立。
    0≤i<n0\le i<n

堆序性质：最高危优先的分诊

急诊室的规则只有一条：最危重的病人永远躺在 1 号床。更精确地说，任何一张床上的病人，病情都比它下面的两张子床更重——至于同一层的两个床位谁更重，小周从来不管。这个“只管上下、不管左右”的局部规则，叠在一起却产生了惊人的全局效果：全楼最危重的病人必然浮在 1 号床。

计算机里，这条规则叫“堆序性质”。最大堆要求每个父结点都不小于它的孩子结点，因此堆顶（数组第一个元素）就是全局最大值；最小堆则相反，每个父结点都不大于孩子，堆顶是全局最小值。注意，堆不是排序数组：兄弟之间谁大谁小没有约束，中间层也可能藏着比某些上层更大的数。

这个性质让优先队列变得极其实用：想要“最紧急的病人”，永远只需看 1 号床，这是 O(1) 的读取；想要维护秩序，只需要在父子之间做比较与交换，不需要关心兄弟。相比完全有序的结构，堆用更宽松的约束换来了更快的维护速度。

小周从不检查同层病床的高低，因为她知道，只要每对父子都遵循“父重子轻”，最危重的病人就不可能藏在别处。全局的极值，来自一条简单到极致的局部规则——这就是堆序性质的魅力。

∀i>0:A[⌊i−12⌋]≥A[i]\forall i>0:\quad A\left[\left\lfloor \displaystyle\frac{i-1}{2}\right\rfloor\right]\ge A[i]
这个公式是最大堆的“家规”：每一个非根结点，都打不过它的父结点。最小堆只需把 ≥ 换成 ≤。
  1. 遍历所有非根结点从 1 号下标开始检查，保证每个孩子结点都满足规则。
    ∀i>0\forall i>0
  2. 取出父结点用寻亲公式找到第 i 个结点的父结点下标。
    p=⌊i−12⌋p=\left\lfloor \displaystyle\frac{i-1}{2}\right\rfloor
  3. 父不小于子最大堆要求父结点的值大于等于子结点的值，层层传递后，根就是最大值。
    A[p]≥A[i]A[p]\ge A[i]

建堆算法：开诊前的全院排序

清晨七点，救护车送来了七位病人，白板上的登记顺序乱七八糟。小周没有时间把病人一个个地“上浮”插入——那要花 O(n log n) 的功夫。她选择从最后一排床位开始，一处一处“安顿”：病情轻的往下挪，病情重的留在上面，从下到上把所有非叶床位各下沉一遍。等她走到 1 号床时，整块白板已经自动成为一张合格的分诊图。

这个算法由弗洛伊德（Floyd）提出，叫“自底向上建堆”。原理很简单：叶子结点没有孩子，天然满足堆序；从最后一个非叶结点（下标 ⌊n/2⌋−1）开始，对每个结点执行下沉操作，直到根结点。每下沉一个结点，它和它的子孙子树就重新满足堆序；处理完根，整棵树都满足堆序。

直觉上这像 O(n log n)，但数学给出了更漂亮的答案：越靠近底层的结点数量越多，但它们能下沉的高度越浅；越靠近根部的结点能下沉很深，但数量只有一两个。两层因素互相抵消，总工作量被“压在”线性级别。

小周在下班前只需从底层到顶层走一遍，整块登记板就井然有序——这比让每位病人重新挂号排队快得多。理解了“多数结点靠近底层、下沉很浅”这一点，你就抓住了 Floyd 建堆 O(n) 的灵魂。

T(n)=∑h=0⌊log⁡2n⌋n2h+1⋅h≤n2∑h=0∞h2h=O(n)T(n)=\sum_{h=0}^{\lfloor \log_2 n\rfloor} \frac{n}{2^{h+1}}\cdot h\le \frac{n}{2}\sum_{h=0}^{\infty}\frac{h}{2^{h}}=O(n)
这个求和公式是建堆效率的“结算单”：每一层贡献的工作量随 h 指数衰减，总和收敛成常数倍 n，所以建堆是 O(n)。
  1. 按层聚合工作量把结点按“到叶子的距离 h”分组，距离为 h 的结点大约有 n/2 的 h+1 次方个。
    n2h+1\displaystyle\frac{n}{2^{h+1}}
  2. 单个结点代价距离叶子 h 层的结点，下沉时最多走 h 步，每一步比较并交换一次。
    ⋅h\cdot h
  3. 求和上限树高最多是 log₂n，h 从 0 取到 log₂n。
    ∑h=0⌊log⁡2n⌋\sum_{h=0}^{\lfloor \log_2 n\rfloor}
  4. 级数收敛等比级数 ∑h/2^h 收敛到 2，所以整体被常数 1 倍 n 控制住。
    ≤n2∑h=0∞h2h=O(n)\le \frac{n}{2}\sum_{h=0}^{\infty}\frac{h}{2^{h}}=O(n)

上浮下沉：新病人与出院处理

午间高峰，救护车又送来一位危重病人。小周不慌不忙：先在白板末尾加一张床位，写上病情指数，然后让这位病人一层一层“升级”——只要比父床更重，就和父床交换位置，直到打不过父床为止。这就是插入操作的“上浮”。几秒后，病人停在属于自己的床位，堆序重新成立。

另一边，1 号床的病人病情好转要出院。直接搬走 1 号床会留下空洞，小周的做法是：把末尾床位的病人临时挪到 1 号床，然后让 TA 一层一层“降级”——在两个孩子中选病情更重的那个，如果比 TA 重就交换，直到两个孩子都打不过 TA。这就是删除堆顶的“下沉”。上浮和下沉，是堆所有操作的两大基本功。

这两条路径都从某个结点走到叶子（或走到根），走的步数恰好是树高。n 个元素的完全二叉树高为 ⌊log₂n⌋，所以插入和删除都是 O(log n)，而读取堆顶只是看一眼 1 号床，是 O(1)。

小周的登记板之所以高效，是因为每一位病人都只在“家族小范围”内移动，从不惊动整层楼。上浮与下沉让堆在动态变化中始终保持秩序，这正是优先队列可以在实时系统中稳定工作的原因。

C(n)≤⌊log⁡2n⌋=O(log⁡n)C(n)\le \lfloor \log_2 n\rfloor=O(\log n)
上浮或下沉最多比较“树高”次。急诊室病人再多，新病人找到床位也不会超过 log₂n 次“家庭会议”。
  1. 路径长度完全二叉树 n 个结点时，从叶子到根的最长边数是 ⌊log₂n⌋。
    ⌊log⁡2n⌋\lfloor \log_2 n\rfloor
  2. 单步成本上浮每层比较一次父结点；下沉每层比较两个孩子取较重者，再与父比较，都是常数次比较。
    O(1)O(1)
  3. 总成本常数次比较乘以最长路径长度，得到对数级复杂度。
    O(1)×O(log⁡n)=O(log⁡n)O(1)\times O(\log n)=O(\log n)

堆排序原理：按病情从重到轻出院

傍晚，小周想把七位病人按病情从重到轻列一份交接清单。她灵机一动：既然 1 号床永远是最危重的，那就把 TA 和末尾床位交换——末尾从此进入“出院区”，不再参与分诊；再把临时挪到 1 号床的病人下沉回合适位置。循环 n−1 轮，白板从 1 号到 7 号床恰好按病情从重到轻排列。

这就是堆排序：先建堆，然后反复“交换堆顶与末尾 + 对剩余区间下沉”。整个过程完全在原数组内完成，不需要额外开一个数组，所以它是原地排序。但要注意，堆排序是不稳定的——两个病情相同的病人，可能在长距离交换中前后顺序颠倒。

堆排序的复杂度很好算：建堆花 O(n)，之后 n−1 轮，每轮下沉花 O(log n)，所以总时间是 O(n log n)。它和快速排序、归并排序同级，但堆排序的最坏情况也是 O(n log n)，没有快速排序那种退化风险，同时又不占额外内存。

小周把这张从重到轻的清单交给下一班护士时，甚至没有多拿一张纸——她在原来的白板上就完成了全部排序。理解堆排序，你就掌握了“利用已有结构就地完成任务”的工程智慧。

T(n)=O(n)+(n−1)⋅O(log⁡n)=O(nlog⁡n)T(n)=O(n)+(n-1)\cdot O(\log n)=O(n\log n)
堆排序的账单：一次 O(n) 的建堆，加上 n−1 次 O(log n) 的下沉。两个部分相加，主导项是 O(n log n)。
  1. 建堆成本先用 Floyd 算法把无序数组整理成堆，这一步是 O(n)。
    Tbuild(n)=O(n)T_{\text{build}}(n)=O(n)
  2. 循环轮数每轮固定一个最大值到末尾，共执行 n−1 轮。
    n−1n-1
  3. 每轮调整交换堆顶后，对长度减少 1 的堆做一次下沉，代价 O(log n)。
    O(log⁡n)O(\log n)
  4. 合并总代价线性项被对数项吞并，最终复杂度为 O(n log n)。
    O(n)+(n−1)O(log⁡n)=O(nlog⁡n)O(n)+(n-1)O(\log n)=O(n\log n)

堆变体对比：不同规模的急诊室选型

小诊所的登记板用二叉堆就够了，但大医院的情况完全不同：医生要频繁地降低某个病人的优先级（比如病情好转），还要合并两个急诊室的登记板。于是出现了“多床位并行”的 d 叉堆：每个床位有 d 个孩子，树更矮，插入更快，但下沉时要比较的孩子也更多。再复杂一点的重症中心用斐波那契堆，它把“账本”记得更精细，让插入、合并、降低优先级这些操作在长期平均意义下接近 O(1)。

d 叉堆中，每个结点有 d 个孩子，树高变成 log 以 d 为底 n，所以插入只需 O(log_d n)；但下沉时每层要比较 d 个孩子，代价是 O(d log_d n)。当 d 增大，插入更快、弹出更慢；d=2 就是最常见的二叉堆，d 取 4 左右时 cache 友好性较好。

斐波那契堆则用“懒账本”策略：平时不急着整理结构，把工作积攒到弹出堆顶时一次性清算。于是插入摊还 O(1)，降低优先级摊还 O(1)，只有弹出堆顶摊还 O(log n)。这特别适合 Dijkstra 这类“频繁降低优先级、偶尔弹出”的场景。

小周最终为不同医院推荐了不同登记板：小诊所用普通二叉堆，调度频繁的急救中心用 4 叉堆，重症科研中心用斐波那契堆。数据结构没有银弹，只有和业务读写频率匹配的选择。

Tpush(d,n)=O(log⁡dn),Tpop(d,n)=O(dlog⁡dn)T_{\text{push}}(d,n)=O(\log_d n),\qquad T_{\text{pop}}(d,n)=O(d\log_d n)
d 叉堆的“选型公式”：d 越大，上浮越浅、插入越快；但下沉时要比的孩子越多、弹出越慢。没有免费的午餐。
  1. 树高公式d 叉堆每一层结点数是 d 的幂，所以 n 个结点的树高是 log 以 d 为底 n。
    log⁡dn\log_d n
  2. 插入成本上浮路径经过树高这么多个父结点，每层比较一次，总成本 O(log_d n)。
    O(log⁡dn)O(\log_d n)
  3. 弹出成本下沉每层要从 d 个孩子中选出最大者，需要 d 次比较，再乘以层数。
    O(dlog⁡dn)O(d\log_d n)

典型应用：Top-K 与 Dijkstra

深夜的调度中心请求支援：从十万份伤情单里挑出最危重的 3 份。小周拿出一个只能登记 3 个床位的小白板（容量 K 的最小堆），每来一份伤情单，就和白板上病情最轻的那位比较，更重就替换。全部扫完，白板上的 3 位就是 Top-3。这就是海量数据 Top-K 的标准解法：复杂度 O(n log K)，内存只有 K。

另一个经典的场景是导航：救护车要从医院开到事故点，路上每个路口都在地图上标记“当前估计最短时长”。小周用最小堆维护这些估计值，每次弹出堆顶（当前最短的候选路口）并固定它，再更新它邻居的估计时长。这个 Dijkstra 算法，整体复杂度是 O((V+E) log V)，其中 V 是路口数，E 是道路数。

堆的作用远不止这些：操作系统按优先级调度进程、GPU 任务队列挑最紧急的请求、AI 推理服务在候选词中选 Top-K——所有“不断有元素进来，又要随时取出极值”的系统，背后都站着一张“急诊室登记板”。

小周把这块小白板递给调度中心时，所有人都惊叹：十万份伤情单，三分钟就筛出了最危重的三人。从急诊室到导航、从操作系统到 AI 推理，优先队列用一张“登记板”撑起了无数实时系统的天花板。

TTop-K(n,K)=O(nlog⁡K)T_{\text{Top-K}}(n,K)=O(n\log K)
Top-K 的时间账单：每个元素只需和大小为 K 的堆顶比较，最坏替换一次并调整，所以总代价是 n 次 O(log K)。
  1. 扫描全部数据对 n 个元素逐个过一遍，每个元素处理成本是 O(log K)。
    n×O(log⁡K)n\times O(\log K)
  2. 小堆维护门槛堆顶是当前第 K 大，新元素比它大才替换，保证堆中永远是最优的 K 个。
    O(log⁡K)O(\log K)
  3. 合并总成本线性扫描乘以对数维护成本，得到 O(n log K)。
    O(nlog⁡K)O(n\log K)

AI 应用场景

大模型推理的 Top-K 采样

阶段：推理与解码

解决的问题：生成文本时，词表通常有几万到几十万个候选词，每次都要从中挑出概率最高的 K 个候选做采样；如果对所有候选排序，成本太高。用容量为 K 的最小堆维护“当前概率最高的 K 个词”，每来一个候选就和堆顶比较，O(log K) 内完成筛选，把解码延迟降到最低。

具体案例：在自回归语言模型推理中，对词表输出的 logits 做 Top-K 过滤时，先建立一个大小 K=50 的最小堆，遍历词表依次替换堆顶，最终堆里的 50 个词就是采样候选集，再经 softmax 重归一化后采样。

难例挖掘中的优先队列

阶段：数据准备与训练

解决的问题：目标检测等任务中，训练样本里简单负样本占比极高，模型很快就能学会，真正有帮助的是那些“难分”的样本。传统做法是每轮随机抽样，浪费大量算力。用优先队列维护损失最高的 K 个样本，让模型持续吃“最难啃的骨头”，训练效率大幅提升。

具体案例：在 OHEM（在线难例挖掘）中，模型前向得到每个候选框的损失，用一个最大堆保留当前批次损失最高的 K 个样本作为训练子集，其余简单样本直接丢弃，使收敛速度和最终精度都显著改善。

GPU 任务调度与路径规划

阶段：模型服务与系统调度

解决的问题：推理集群中，有的请求来自在线交易必须秒回，有的来自离线批处理可以排队。用优先队列按优先级和截止时间调度任务，保证关键请求先被处理；在具身智能的路径规划里，Dijkstra 配合最小堆计算最短路径，让机器人快速到达目标点。

具体案例：某自动驾驶公司用最小堆维护路口节点“当前最短距离估计”，每个节点被弹出一次即被确认，更新邻居后重新入堆，最终在 O((V+E) log V) 时间内规划出最优路线。

Python 演示

python67 行
# -*- coding: utf-8 -*-class MaxHeap:    def __init__(self, data=None):        self.a = list(data) if data is not None else []        if self.a:            for i in range(len(self.a) // 2 - 1, -1, -1):                self._sink(i, len(self.a))     def _sink(self, i, n):        while True:            l, r, big = 2 * i + 1, 2 * i + 2, i            if l < n and self.a[l] > self.a[big]:                big = l            if r < n and self.a[r] > self.a[big]:                big = r            if big == i:                break            self.a[i], self.a[big] = self.a[big], self.a[i]            i = big     def _float(self, i):        while i > 0:            p = (i - 1) // 2            if self.a[i] <= self.a[p]:                break            self.a[i], self.a[p] = self.a[p], self.a[i]            i = p     def push(self, x):        self.a.append(x)        self._float(len(self.a) - 1)     def pop(self):        top = self.a[0]        last = self.a.pop()        if self.a:            self.a[0] = last            self._sink(0, len(self.a))        return top     def peek(self):        return self.a[0]  def heap_sort(nums):    h = MaxHeap(nums)    out = []    while h.a:        out.append(h.pop())    return out  def top_k(nums, k):    import heapq    heap = nums[:k]    heapq.heapify(heap)       # 最小堆,堆顶是当前第k大的门槛    for x in nums[k:]:        if x > heap[0]:            heapq.heapreplace(heap, x)    return sorted(heap, reverse=True)  if __name__ == "__main__":    arr = [3, 1, 4, 1, 5, 9, 2, 6]    print("heap  :", MaxHeap(arr).a)    print("sort  :", heap_sort(arr[:]))    print("top3  :", top_k(arr, 3))
目的：实现一个最大堆（含 Floyd 建堆、插入上浮、删除下沉），并演示堆排序和 Top-K 两个经典应用。
  1. for i in range(len(self.a) // 2 - 1, -1, -1):从最后一个非叶结点开始自底向上建堆，叶子天然满足堆序不用管。
  2. self._sink(i, len(self.a))下沉操作：在两个孩子里选更大的那个，若比当前结点大就交换，一直沉到合适位置。
  3. p = (i - 1) // 2上浮时用寻亲公式定位父结点，这是堆数组表示的核心换算。
  4. if self.a[i] <= self.a[p]: break一旦自己打不过父结点就停止上浮，维持堆序的收敛条件。
  5. top = self.a[0]堆顶是全局极值，peek 操作只需要 O(1) 读数组第一个元素。
  6. last = self.a.pop()弹出末尾元素临时顶上，保证数组依旧紧凑无空洞。
  7. heapq.heapify(heap)Python 内置最小堆原地建堆，同样只有 O(K) 的代价。
  8. if x > heap[0]: heapq.heapreplace(heap, x)新元素比堆顶（当前第 K 大）大才替换，Top-K 的核心门槛逻辑。

常见误区

误区我刚开始学堆时，以为最大堆的数组就是从左到右从大到小排好序的，就像 `[9, 8, 7, 6, 5]` 那样。

正解堆只保证“父结点大于等于子结点”的父子序，兄弟之间完全无序。比如 [9, 8, 7, 5, 4, 6, 3] 是合法最大堆，但 6 排在 5 后面仍然没问题。就像急诊室只保证父母比孩子病重，从不要求同层病床按病情排序。堆用更宽松的约束换来了更快的维护速度。

为何常见：人们习惯把“树”想象成有序结构，加上堆排序输出的结果是有序的，就误以为堆内部也有序。实际上“堆是有序树的抽象”这一印象混淆了堆与二叉搜索树。

误区我以为每插入一个元素要 O(log n)，插 n 个就是 O(n log n)，所以建堆不可能更快。

正解Floyd 自底向上建堆不是“逐个插入”，而是从最后一个非叶开始逐个下沉。多数结点靠近叶子，下沉路径很短；数学上每层的工作量按 1/2 的幂衰减，总和收敛到 O(n)。就像小周从最后一排床位开始安顿，大部分病人只挪一两层就到位，而不是每个人都要从顶层走到叶子。

为何常见：初学者把“插入建堆”和“Floyd 建堆”混为一谈，忽略了叶子结点无需处理这个关键事实，也缺少对等比级数求和收敛的直觉。

误区我以为堆排序和插入排序一样稳定，因为看起来只是不断交换相邻的父子结点。

正解堆排序是典型的不稳定排序。堆顶与末尾元素交换是“远距离跳变”，可能把两个值相等的元素相对顺序打乱。比如两个病情相同的病人，一个在堆顶附近，一个在底层，交换后先后顺序可能颠倒。这正是面试中区分“稳定”与“不稳定”的经典案例。

为何常见：只看到堆内部是父子交换，忽略了堆顶与末尾的长距离交换；也没有意识到“稳定”要求的是相等元素在整个排序过程中保持原相对次序。

误区既然要最大的 K 个，直觉上应该维护一个最大堆，把堆顶不断输出。

正解求“最大 K 个”时，更省内存的做法是维护容量为 K 的最小堆：堆顶是“当前第 K 大的门槛”，任何新元素只有比门槛大才替换进去。这样只需 O(K) 内存、O(n log K) 时间。如果用最大堆，必须把全部 n 个元素都存进堆，内存和成本都更高。就像小周只留一块能登记 3 个床位的小白板，而不是把十万份伤情单全贴到墙上。

为何常见：直觉会跟着“最大”走，忽略了问题的本质是“在海量数据中筛子集”，关键优化点是控制存储规模，而不是追求堆的方向。

面试题

Q1. 在一个最大堆中，堆顶元素是什么？

单选题 · easy

  • A.数组中最小的元素
  • B.数组中最大的元素← 正确答案
  • C.数组中间位置的元素
  • D.任意一个叶子结点

答案：B。最大堆的堆序性质要求每个父结点都不小于子结点，层层递推后，根结点必然是全局最大值。堆顶就是数组第一个元素，读取它只需 O(1)。其余选项要么违反堆序性质，要么与堆顶定义无关。

Q2. 数组 [10, 9, 8, 7, 6, 5, 4] 是否满足最大堆的结构要求？

单选题 · easy

  • A.满足← 正确答案
  • B.不满足
  • C.无法判断
  • D.取决于数组长度

答案：A。数组下标从 0 开始，父结点下标为 ⌊(i−1)/2⌋。检查每个非根结点：9≤10、8≤10、7≤9、6≤9、5≤8、4≤8，全部满足“父不小于子”，且完全二叉树无空洞，因此是合法最大堆。

Q3. 在数组表示的堆中，下标为 5 的结点的左孩子下标是多少？

单选题 · easy

  • A.9
  • B.10
  • C.11← 正确答案
  • D.12

答案：C。左孩子下标公式为 left(i) = 2i + 1，代入 i = 5 得 2×5+1 = 11。右孩子才是 12。若用 1 起始下标则公式不同，但标准实现从 0 开始，11 是唯一正确选项。

Q4. 用 Floyd 算法对 n 个元素原地建堆的时间复杂度是？

单选题 · mid

  • A.O(n log n)
  • B.O(n)← 正确答案
  • C.O(log n)
  • D.O(n²)

答案：B。Floyd 从最后一个非叶结点开始自底向上下沉。虽然直觉像 O(n log n)，但多数结点靠近叶子、下沉深度浅，总工作量是收敛的等比级数，严格推导得到 O(n)。逐个插入才是 O(n log n)，两者不要混淆。

Q5. 用容量为 K 的最小堆求海量数据中最大的 K 个值，时间复杂度是？

单选题 · mid

  • A.O(K log n)
  • B.O(n log K)← 正确答案
  • C.O(n)
  • D.O(n log n)

答案：B。每个元素只需和堆顶（当前第 K 大的门槛）比较，最坏情况下替换并调整堆，调整代价为 O(log K)。遍历 n 个元素总代价为 O(n log K)。这个方案内存只有 O(K)，是海量 Top-K 的标准解法。

Q6. 有 15 个元素的堆，向其中插入一个新元素，最多需要比较多少次？

单选题 · mid

  • A.3← 正确答案
  • B.4
  • C.15
  • D.16

答案：A。15 个结点的完全二叉树高为 ⌊log₂15⌋ = 3（根为第 0 层）。新元素从叶子一路上浮，每上升一层与父结点比较一次，最多经过 3 个父结点，所以最多比较 3 次。比较次数等于树高，不是结点数。

Q7. 关于堆排序，下列说法正确的是？

单选题 · hard

  • A.堆排序是稳定排序
  • B.堆排序是不稳定排序← 正确答案
  • C.堆排序最坏时间复杂度为 O(n²)
  • D.堆排序需要额外 O(n) 内存

答案：B。堆排序通过堆顶与末尾长距离交换完成“固定极值”，这种远距离跳变可能打乱相等元素的相对顺序，因此不稳定。它的最坏、平均、最好时间复杂度都是 O(n log n)，且是原地排序，不需要额外 O(n) 内存。

Q8. 关于 n 个元素的二叉堆操作复杂度，下列说法正确的有？

多选题 · mid

  • A.查看堆顶是 O(1)← 正确答案
  • B.插入元素是 O(log n)← 正确答案
  • C.弹出堆顶是 O(n)
  • D.Floyd 建堆是 O(n)← 正确答案

答案：ABD。堆顶是数组第一个元素，查看是 O(1)；插入走“尾部上浮”，路径长度等于树高，是 O(log n)；弹出堆顶后做一次下沉，也是 O(log n)，不是 O(n)；Floyd 自底向上建堆经级数求和为 O(n)。

Q9. 给定数组 [9, 7, 8, 5, 4, 6, 3]，下列说法正确的有？

多选题 · hard

  • A.它是一个合法的最大堆← 正确答案
  • B.根结点是全局最大值← 正确答案
  • C.兄弟结点之间一定有序
  • D.数组紧密无空洞，可直接用于堆← 正确答案

答案：ABD。逐对检查父子关系，均满足父不小于子，是合法最大堆；堆序性质保证根 9 是最大值；兄弟之间（如 7 与 8）无序，这是堆与排序数组的本质区别；完全二叉树的数组表示天然紧凑、无空洞。

Q10. 关于斐波那契堆的摊还复杂度，下列说法正确的是？

单选题 · extreme

  • A.插入元素摊还 O(log n)
  • B.弹出堆顶摊还 O(log n)← 正确答案
  • C.查看堆顶摊还 O(log n)
  • D.合并两个堆摊还 O(n)

答案：B。斐波那契堆用“懒账本”策略，插入和合并都摊还 O(1)，降低优先级也摊还 O(1)；只有弹出堆顶需要整理根表并做级联剪枝，摊还 O(log n)。查看堆顶只需读指针，是 O(1)。它适合频繁插入、合并、降级但较少弹出的场景，如 Dijkstra 算法。