想象你是一栋 24 层“资历大厦”的新任物业经理。大厦有个奇特规矩：工号数字越大的人，必须住在越高的楼层。于是，任何人抬头，都能看见楼上住着工号比自己大的人，顶楼永远住着全楼最资深的员工。这栋大厦的入住规则，就是计算机世界里“大顶堆”的样子。招聘、换房、调整、退休——堆排序的每一步，都像物业经理在安排整栋大厦的入住。它不追求一步到位的优雅，而是靠“大数字住高层”这一条简单规则，反复执行同一种调整动作，最终让整栋大厦从顶楼到底楼按资历从高到低排好。整个过程雷打不动地消耗 O(n log n) 步，却几乎不占额外的房间。

岗位关联

掌握堆排序，你就拿到了理解优先队列、Top-K 热榜、Dijkstra 最短路径等工程场景的钥匙，更是面试中“最坏情况也不翻车”的排序底气。

目录
  1. 可视化演示
  2. 堆的定义：资历大厦的入住规则
  3. 数组存储：大厦的编号系统
  4. 下沉操作：住错楼层的降级流程
  5. 建堆过程：从底层开始的团队重整
  6. 排序流程：把资深员工一个个请进退休区
  7. 复杂度分析：效率账本
  8. 对比与应用：不同选人策略的博弈
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

动态演示堆排序算法原理与复杂度分析的核心机制，通过开始/执行/监控/完成四种模式展示关键概念与交互流程。

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

堆排序算法原理与复杂度分析：二叉堆的 二叉堆的数组表示与堆性质 自底向上建堆与 O(n) 复杂 核心机制可视化 堆排序算法原理与复杂度分析整体架构与关键组件

堆的定义：资历大厦的入住规则

物业经理上岗的第一天，保洁阿姨就告诉他一句全楼铁律：“楼上工号必须比楼下大，谁也不能例外。”这句铁律听起来简单，却让整栋楼有了一个神奇的性质——顶楼永远住着全楼工号最大的人。无论是找人开会还是决定大事，你只需要看一眼顶楼，就能拿到“现役最强”的答案。这条铁律，就是数据结构中“大顶堆”的核心定义。

在计算机世界里，这栋“资历大厦”叫二叉堆。它首先是一棵完全二叉树：每一层都从左到右填满，最后一层也从左往右连续放置，中间不能有空缺。换句话说，大厦的房间可以一层层从左往右数下去，不会有“某层中间空着”的情况。其次，它满足“堆序性质”：对任意节点，父节点的值不小于它的左、右孩子。如果父节点比孩子小，就违反了大厦铁律，需要立刻调整。

有了这两条规则，我们就能用一个简单的数学表达式描述大厦铁律。对数组中任意节点 i（它的左孩子是 2i+1、右孩子是 2i+2），大顶堆要求：

看，大厦铁律在计算机里就是一行公式。只要每个房间都遵守它，顶楼永远是最资深的人。而这，正是堆排序全部力量的来源——它不需要每次都“大海捞针”般地找最大值，最大值永远自觉地站在顶楼等你。

a[i]≥a[2i+1],a[i]≥a[2i+2]a[i] \ge a[2i+1], \quad a[i] \ge a[2i+2]
这个式子是说：住在 i 房间的人，工号不能小于住在 2i+1 和 2i+2 房间的两个人。只要每个房间都遵守，顶楼自然就是最大工号。
  1. a[i]下标为 i 的房间（节点）里存放的值，可以理解成工号。
    a[i]a[i]
  2. 大于等于号父节点的值不小于子节点，保证“楼上的资历更老”。
    ≥\ge
  3. a[2i+1]下标 2i+1 是 i 的左孩子，即 i 左边隔壁楼层的那个房间。
    a[2i+1]a[2i+1]
  4. a[2i+2]下标 2i+2 是 i 的右孩子，即 i 右边隔壁楼层的房间。
    a[2i+2]a[2i+2]

数组存储：大厦的编号系统

物业经理很快发现，铁律要落地，必须先解决“怎么称呼每个房间”的问题。于是他给大厦设计了一套编号规则：从顶楼开始，一层层从左往右编号，顶楼是 0 号，第二层左 1 号、右 2 号，第三层依次 3、4、5……这套编号规则，就是二叉堆用数组存储的方式。

为什么不用链式结构？因为完全二叉树的形状非常规整，每个房间的位置都能通过简单的算数推算出来。只要知道某个房间的编号 i，就能立刻算出它的上下邻居。这种“用数组保存一棵树”的技巧，让堆几乎不浪费任何存储空间，数组的第几个元素就是树的第几个节点，一一对应。

对物业经理来说，最常用的换算公式有三个：找左孩子、找右孩子、找爸爸。孩子永远分布在下一层，而爸爸永远在上一层。给定节点下标 i，它的左孩子是 2i+1，右孩子是 2i+2，父亲则是 (i-1)/2 的整数部分。用公式表达就是：

有了这套编号系统，物业经理在登记册上随便一指，就知道该去哪个房间查工号。这也是堆排序空间开销极小的秘密：整棵“大厦”就装在一个普通数组里，不需要额外的指针或节点对象，真正做到“一张纸登记全楼住户”。

parent(i)=⌊i−12⌋parent(i) = \left\lfloor \frac{i - 1}{2} \right\rfloor
无论从哪个房间出发，向上找一层，用 i-1 除以 2 再向下取整，就能找到楼上的家人。
  1. i当前房间的编号，也就是数组下标。
    ii
  2. i-1从当前房间编号回退 1，用于统一左、右孩子反推父亲的差异。
    i−1i - 1
  3. 除以 2上一层节点数是下一层的一半，所以向上走一层就除一次 2。
    i−12\frac{i - 1}{2}
  4. 向下取整符号左右孩子在整数除法下会落在同一个区间，取整后得到唯一的父节点下标。
    ⌊⋅⌋\left\lfloor \cdot \right\rfloor

下沉操作：住错楼层的降级流程

有一天，一位工号 5 的新员工因为人事录入错误，被安排进了顶楼。整栋大厦的住户怨声载道：“楼上工号比楼下小，铁律被破坏了！”物业经理的补救办法很朴素：让 5 号一路往下换，直到找到属于他的楼层。这个过程，就是堆排序的核心动作——下沉（sift down）。

下沉的具体流程像一场“楼层淘汰赛”：先看看这位住错楼层的人两个孩子里，谁的工号更大（如果孩子工号都比他小，那他就已经合格了，不用动）；然后让 5 号跟较大的孩子交换房间；交换后，他可能依然比新楼层的孩子小，那就继续重复“比孩子、换房间”的循环，直到他到达一个两孩子都不如自己的位置。整个过程就像掉进井里的石头，一路磕磕碰碰落到井底。

用数学语言描述一次比较：假设当前作弊者站在下标 i，他的两个候选对手是左孩子 2i+1 和右孩子 2i+2。我们要从这三个房间中找出工号最大的那个，作为交换对象：

如果最大值就是当前的 a[i]，说明他已经打赢了所有孩子，下沉结束；否则，就把他和最大的孩子交换，再继续下一轮比较。每一次下沉最多沿着树的高度走到底，所以单次下沉的时间不超过树的层数 O(log n)。这个“错楼层员工降级”的流程虽然朴实，却是堆无数次自我修复的基石——整栋大厦的所有秩序，都靠这一招反复执行来维持。

max⁡(a[i],a[2i+1],a[2i+2])\max(a[i], a[2i+1], a[2i+2])
  1. a[i]当前正在下沉的节点值，即住错楼层的工号。
    a[i]a[i]
  2. a[2i+1]左孩子的值，它可能比当前节点大，也可能小。
    a[2i+1]a[2i+1]
  3. a[2i+2]右孩子的值，它是另一个候选对手。
    a[2i+2]a[2i+2]
  4. max 取最大三选一，谁最大谁就该待在更上面的位置。
    max⁡(⋅)\max(\cdot)

建堆过程：从底层开始的团队重整

新大厦落成那天，住户是随机入住的，整栋楼完全不符合铁律。物业经理面临一个难题：如何用最少的力气，让全楼从无序变为有序？聪明的做法不是从顶楼开始调整，而是从倒数第二层开始，逐层向上做下沉。为什么？因为对最底层（叶层）的员工来说，他们本来就没有孩子，天然就是“合格”的。

“从倒数第二层开始”背后的数字是 n/2 - 1，这是最后一个非叶子节点的下标。从它开始，往前逐个做下沉操作，每处理完一个节点，以它为根的子树就变成一个小堆；当处理到根节点时，整棵树就都是大顶堆了。这个自底向上的过程，像工人们在盖楼时先一层层夯实地基——底下的楼层先自洽，上面的调整才有支撑。

你可能直觉上觉得，每个节点都做一次下沉，那总时间应该是 O(n log n)。但数学家发现了这栋大厦的秘密：越靠近底层的节点数量越多，但它们能下沉的高度越短；越靠近顶层的节点能下沉很远，但数量极少。把每一层的“节点数 × 下沉高度”加起来，总量恰好被压缩成线性：

建堆的“自底向上”策略，正好对应物业经理的智慧：先让底层的小团队各自形成规范，再逐级合并成大团队。每一级的新领导只需要下沉很短的距离就能适应岗位。整栋大厦的“入职整顿”因此高效得惊人——这也是堆排序相比其他排序最先让人眼前一亮的地方。

T(n)=∑h=0⌊log⁡2n⌋n2h+1⋅h=O(n)T(n) = \sum_{h=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^{h+1}} \cdot h = O(n)
底层人数虽多但走不了几步，顶层走得远但人少，两相抵消，建堆的总工作量只是 O(n)，比想象中便宜得多。
  1. h 从 0 到 log₂nh 表示从叶层往上数的层号，叶层 h=0，越往上 h 越大。
    ∑h=0⌊log⁡2n⌋\sum_{h=0}^{\lfloor \log_2 n \rfloor}
  2. n / 2^{h+1}第 h 层的节点数量，越往上的层节点数越少。
    n2h+1\frac{n}{2^{h+1}}
  3. 乘以 h该层每个节点最多下沉 h 层，是单节点的下沉成本。
    ⋅h\cdot h
  4. 结果为 O(n)级数求和后收敛为线性，因为越上层节点越少，那些“下沉很远”的节点数量少得可以忽略。
    =O(n)= O(n)

排序流程：把资深员工一个个请进退休区

大厦建成、铁律恢复后，真正的排序才刚刚开始。物业经理的终极目标，是让整栋楼从顶楼到底楼按工号从大到小整齐排列。他祭出的办法简单得可爱：每次把顶楼最资深的人请去“退休区”，然后让新人重新顶上。

具体操作分四步循环：第一步，把堆顶（当前最大工号）和堆的最后一个元素交换，于是最大值被送到了数组末尾，那里成为“退休区”（已排序区）；第二步，把堆的长度减一，退休区的员工不再参与大厦管理；第三步，被换到顶楼的新员工工号通常很小，需要执行一次下沉操作，让大厦重新满足铁律；第四步，不断重复以上过程，直到堆里只剩下一个住户。此时，整个数组从前往后看就是从小到大的升序——因为每次都是从大到小“请出”了最大值。

每一轮排序都包含一次 O(1) 的交换和一次 O(log n) 的下沉。排序阶段要执行 n-1 轮，当堆越来越小时，下沉的成本也越来越低。累计起来，排序阶段的总工作量是：

这就像一个循环往复数钱的过程：每次都把最大的一张钞票抽出来放到一边，再把剩下的钞票重新整理成“顶楼最大”的秩序。虽然每次整理都要花点功夫，但总共只整理 n-1 次，整体开销依然非常可控——堆排序的核心循环，就这样优雅地完成了全部排序任务。

T(n)=∑k=2nO(log⁡k)=O(nlog⁡n)T(n) = \sum_{k=2}^{n} O(\log k) = O(n \log n)
从 n 开始一路缩减到 2，每一轮的成本都不超过 log n，加起来就是 n 乘以 log n 量级。
  1. k 从 2 到 nk 表示当前堆的大小，每轮排序后堆缩小 1。
    ∑k=2n\sum_{k=2}^{n}
  2. O(log k)在大小为 k 的堆中做一次下沉的成本，与堆高成正比。
    O(log⁡k)O(\log k)
  3. 累加所有轮次把 n-1 轮的下沉成本全部加起来。
    ∑k=2nO(log⁡k)\sum_{k=2}^{n} O(\log k)
  4. 等于 O(n log n)对数和的总和渐近等于 n log n，这就是排序阶段的时间上界。
    =O(nlog⁡n)= O(n \log n)

复杂度分析：效率账本

年底总结时，物业经理拿出账本，核对了整栋大厦一年来的所有操作。堆排序的总时间由两部分构成：建堆 O(n) 加上 n-1 次下沉 O(n log n)，两者相加仍是 O(n log n)。更关键的是，这个复杂度不随输入数据的初始顺序而波动——无论数组原本是升序、降序还是乱序，堆排序的效率都稳如泰山，不会出现快排那样“最坏退化到 O(n²)”的翻车时刻。

空间账本同样漂亮：堆排序是在原数组内做交换，只用了常数个临时变量（交换用），没有申请额外的大块内存，因此空间复杂度是 O(1)。这是它与归并排序最大的分野——归并排序虽然稳定，却必须额外开辟一块和原数组一样大的空间来“归档”。

总时间和总空间写在一起，就是堆排序的完整效率画像：

不过，工号交换意味着相同工号的两个人可能被调换相对顺序。举个极端例子：两个工号同为 30 的员工，一个在左一个在右，排序后右边的可能跑到左边——所以堆排序是不稳定的。这就像大厦搬家时，两件相同重量的行李可能互换了位置。好在大厦不需要关心这个细节，只要最终数值有序即可。堆排序这份账本，算得上“时间稳健、空间节俭”，唯一的瑕疵就是不稳定。

T(n)=O(n)+O(nlog⁡n)=O(nlog⁡n),S(n)=O(1)T(n) = O(n) + O(n \log n) = O(n \log n), \quad S(n) = O(1)
建堆的线性时间 + 排序阶段的 n log n 时间，构成效率总账；全程只占用常数级额外空间。
  1. O(n)建堆阶段的开销，自底向上的下沉总和是线性的。
    O(n)O(n)
  2. O(n log n)排序阶段 n-1 轮下沉的总开销。
    O(nlog⁡n)O(n \log n)
  3. 相加取主导项线性项被 log 主导，最终时间复杂度是 O(n log n)。
    O(n)+O(nlog⁡n)=O(nlog⁡n)O(n) + O(n \log n) = O(n \log n)
  4. S(n) = O(1)空间复杂度只看额外使用的变量数量，是常数级。
    S(n)=O(1)S(n) = O(1)

对比与应用：不同选人策略的博弈

物业经理把大厦管理经验分享给三位同行，发现大家选人的策略各不相同。快排如同“快刀斩乱麻”的临时主管：平时干活飞快（平均 O(n log n)），但遇到极端楼层布局时可能手忙脚乱，退化到 O(n²)；归并如同“资料归档大师”：做事稳定有序，但每轮都要把资料复制一份到新柜子，空间成本 O(n)；堆排序则像本大厦的铁律执行者：不追求最快，但只靠 O(1) 额外空间，就能承诺“最差情况也不超过 O(n log n)”。

这三种策略的现实选型也有规律可循。如果系统对最坏响应时间有硬性要求（比如实时交易撮合），堆排序的“最坏也有保证”就格外珍贵；如果数据量巨大且内存紧张，堆排序的原位排序能力是救命稻草；如果需要对对象做稳定排序且内存宽裕，归并更合适；大部分通用场景下，快排凭借极小的常数因子胜出，这也解释了为什么语言内置排序多是快排的改良版。

堆排序还有另一个响亮的名号——优先队列的底层引擎。凡是需要“随时取出最大/最小元素”的场景，背后几乎都站着一个堆。用堆实现 Top-K 问题（从海量数据中找最大的 K 个），只需要维护一个大小为 K 的小顶堆，成本只需：

从大厦的管理哲学中，我们学到最重要的一课：当你在乎“最坏情况”而不只是“平均情况”时，堆排序是你最可靠的伙伴。它可能不是最快的，但它用一个小小的堆顶，保证了任何时刻你都能以可预测的成本获取全局最值——这份稳定，正是优先队列、Dijkstra 最短路径、Top-K 热榜等无数工程系统选择它的理由。

T(n,k)=O(nlog⁡k)T(n, k) = O(n \log k)
处理 n 个元素时，堆始终只保留 K 个候选，每次更新只需 log K 的比较。
  1. n需要扫描的全部数据量。
    nn
  2. log k堆中只有 K 个元素，每插入或替换一次的成本只与 K 相关。
    log⁡k\log k
  3. 相乘对 n 个元素各处理一次，总成本就是 n 乘 log k。
    O(nlog⁡k)O(n \log k)

AI 应用场景

大模型推理中的 Top-K 采样

阶段：模型推理阶段，策略采样

解决的问题：大模型生成下一个 token 时，需要从词表中选出概率最高的 K 个候选词做采样。词表可能有上万甚至几十万项，直接全排序非常昂贵；传统做法是排序后取前 K，但排序整个分布浪费了大量计算。

具体案例：以 ChatGPT 生成“今天天气”的续写为例，模型在每一步推理时都会得到一张几十万词的候选概率表。系统用一个大小为 K 的小顶堆扫描这张表，每遇到一个比堆顶概率更高的词就替换堆顶并下沉，最终堆里留下的就是概率最高的 K 个词，整个过程只消耗 O(K) 空间和 O(V·log K) 时间，比全排序快几个数量级。

推荐系统的高频物品热榜

阶段：离线数据处理 / 特征工程

解决的问题：推荐系统需要从用户行为日志中统计“点击率最高的前 100 个物品”，日志可能有上亿条；传统 MapReduce 全量排序既慢又耗内存，堆排序的 Top-K 思路可以只保留一个很小的候选堆。

具体案例：某电商平台的实时排行榜服务，维护一个大小为 100 的小顶堆。每来一条新的点击量数据，就与堆顶比较，如果更大则替换并下沉，始终让最小的候选留在堆顶。这样任何时刻，堆里的 100 个元素就是当前点击量最高的 100 个商品，查询 Top-K 的响应时间稳定在微秒级。

任务调度器的优先队列实现

阶段：训练平台任务调度

解决的问题：AI 训练平台上，成百上千个训练任务提交后，调度器需要按优先级决定哪个任务先拿 GPU 资源。普通队列需要遍历找最高优先级，效率低；用堆实现优先队列，每次“取出最高优先级任务”只需 O(log n)。

具体案例：Kubernetes 调度器中的调度队列就是典型的堆实现：每个 Pod 按优先级入堆，调度循环每次从堆顶取出优先级最高的 Pod 去分配节点，新任务到达时入堆调整的耗时仅为 O(log n)，即使集群中有上万个等待任务，调度延迟也依然可控。

Python 演示

python34 行
def sift_down(arr, n, i):    """从节点 i 开始下沉，维护大顶堆性质"""    while True:        largest = i        left = 2 * i + 1        right = 2 * i + 2        if left < n and arr[left] > arr[largest]:            largest = left        if right < n and arr[right] > arr[largest]:            largest = right        if largest == i:            break        arr[i], arr[largest] = arr[largest], arr[i]        i = largest  def heap_sort(arr):    n = len(arr)    # 建堆：从最后一个非叶子节点开始自底向上下沉    for i in range(n // 2 - 1, -1, -1):        sift_down(arr, n, i)    print("建堆完成:", arr)    # 排序：每次把堆顶最大值换到末尾，再对缩小的堆下沉    for end in range(n - 1, 0, -1):        arr[0], arr[end] = arr[end], arr[0]        sift_down(arr, end, 0)        print("第 %d 轮:" % (n - end), arr)    return arr  if __name__ == "__main__":    data = [4, 10, 3, 5, 1]    heap_sort(data)    print("排序结果:", data)
目的：完整实现大顶堆的建堆、下沉和排序过程，并输出每一步的中间状态，帮助你直观看到“最大值被一个个请到末尾”的过程。
  1. for i in range(n // 2 - 1, -1, -1):从最后一个非叶子节点开始倒着遍历，保证每个子树先变成小堆。
  2. sift_down(arr, n, i)下沉函数，让当前节点一路和较大的孩子交换，直到满足堆性质。
  3. largest = i先假设当前节点就是最大的，再依次跟孩子比。
  4. if left < n and arr[left] > arr[largest]:左孩子存在且更大时，更新最大值为左孩子下标。
  5. if largest == i: break如果最大值还是自己，说明已经到位，提前终止循环。
  6. arr[0], arr[end] = arr[end], arr[0]把堆顶（最大值）与当前末尾交换，相当于“请进退休区”。
  7. sift_down(arr, end, 0)对缩小后的堆重新调整堆顶，准备下一轮。

常见误区

误区听说堆排序用到了“堆”，就以为是程序运行时申请内存的那个“堆区（heap）”，担心堆排序会占用大量动态内存。

正解这是两个完全同名的不同概念。数据结构里的“堆”是一种像大厦楼层一样的树形结构，重点在“父子大小关系”；而内存里的“堆”是操作系统管理动态分配内存的区域。堆排序使用的“堆”只是逻辑上的结构，实际数据仍存储在普通的数组里，不涉及内存堆的动态分配，额外空间仅有常数级 O(1)。

为何常见：英文单词 heap 同时指“堆结构”和“堆内存”，初学者最早接触的是语言运行时概念，遇到数据结构的堆时极易混淆。

误区建堆是对 n 个节点各做一次下沉，每次下沉 O(log n)，所以建堆应该是 O(n log n)，堆排序总时间就该是 2 倍 O(n log n)。

正解账不是这么算的。虽然每个节点都下沉了一次，但绝大多数节点在底层，下沉高度很短。把“每层的节点数 × 下沉高度”求和，越上层节点越少，总和收敛为 O(n)。这就像整栋大厦调整楼层：底层几百人每人只需上下 1-2 层，顶楼那几个人虽要走到很下面，但人数太少，总工作量被拉低到线性。

为何常见：直觉上“n 次操作 × 单次 log n 成本”是乘法思维，忽略了节点数量随高度按指数递减的结构性事实。

误区堆排序每次都是拿堆顶最大值放到末尾，看起来很有序，应该和冒泡、归并一样是稳定排序吧？

正解堆排序不稳定。下沉操作中，值相等的元素可能隔着很远被交换，破坏了原有相对顺序。例如数组 [30a, 30b, 5]，建堆后 30a 和 30b 可能互换位置，排序后 30b 反而跑到了 30a 前面。堆排序只保证“数值有序”，不保证“相等元素先后顺序不变”。

为何常见：人们常把“排序效果好、结果正确”和“稳定”混为一谈，忽略了稳定性是一个只关乎相等元素相对顺序的精细性质。

误区堆排序最坏也是 O(n log n)，快排最坏会退化 O(n²)，所以堆排序应该全面碾压快排，工程上应该优先用堆排序。

正解大 O 复杂度描述的是渐近趋势，真实运行还受常数因子影响。堆排序的“下沉”操作访问内存是跳跃式的（父子下标跨度大），缓存命中率低；快排是顺序扫描 + 交换，缓存友好，常数因子小得多。实测中快排通常比堆排序快 2-5 倍，因此标准库的 sort 多为快排改良版。堆排序的优势不在“快”，而在“最坏可预测 + 空间 O(1)”。

为何常见：初学者只看大 O 忽略了常数因子和缓存局部性，把理论复杂度和实际性能画了等号。

面试题

Q1. 在大顶堆中，根节点（下标 0）存储的一定是什么？

单选题 · easy

  • A.最小值
  • B.最大值← 正确答案
  • C.中间值
  • D.任意值

答案：B。大顶堆的性质是每个父节点都不小于孩子，根节点是所有人的“领导”，层层传递下来，根节点必然是全局最大值。这就像资历大厦的顶楼必然住着全楼最大工号。

Q2. 数组实现的二叉堆中，下标为 i 的节点的左孩子下标是？

单选题 · easy

  • A.i+1
  • B.i-1
  • C.2i+1← 正确答案
  • D.2i+2

答案：C。完全二叉树按层序编号时，父节点 i 的左孩子是 2i+1、右孩子是 2i+2，父节点是 (i-1)/2 向下取整。这是堆结构用数组存储时的基本换算，物业经理靠它快速找房间。

Q3. 对长度为 n 的数组建堆，第一个需要执行下沉操作的非叶子节点下标是？

单选题 · easy

  • A.n-1
  • B.n/2-1← 正确答案
  • C.n/2
  • D.0

答案：B。叶子节点没有孩子，天然满足堆性质，不需要调整。最后一个非叶子节点是最后一个元素 n-1 的父节点，即 (n-1-1)/2 向下取整 = n/2-1。建堆从它开始自底向上逐个下沉。

Q4. 对一个长度为 n 的无序数组建堆，时间复杂度是多少？

单选题 · mid

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

答案：A。自底向上建堆时，底层节点数量多但下沉高度短，顶层节点能下沉很远但数量极少。把“节点数 × 下沉高度”按层求和会收敛为 O(n)。这就像调整大厦楼层，底层人虽多但每人只走一两层，总工作量是线性的。

Q5. 堆排序中，单次“下沉”操作在大小为 n 的堆上的最坏时间复杂度是？

单选题 · mid

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

答案：B。一次下沉从某个节点出发，每轮交换一次就下降一层，最多走到叶子。完全二叉树的高度为 log₂n，所以最坏情况下比较和交换次数是 O(log n)。像工号 5 一路从顶楼沉到底楼，步数不超过楼层数。

Q6. 下列关于堆排序的说法，正确的有哪些？

多选题 · mid

  • A.空间复杂度为 O(1)← 正确答案
  • B.属于稳定排序
  • C.是原地排序← 正确答案
  • D.平均时间复杂度为 O(n log n)← 正确答案

答案：ACD。堆排序在原始数组内交换元素，额外空间只有常数级临时变量，是原地排序且空间 O(1)，A、C 正确；平均和最坏时间都是 O(n log n)，D 正确。但下沉的远距离交换会破坏相等元素相对顺序，所以它不稳定，B 错误。

Q7. 堆排序和快速排序相比，堆排序最独特的优势是什么？

单选题 · hard

  • A.平均时间复杂度更低
  • B.天然稳定排序
  • C.最坏情况仍保持 O(n log n) 且空间 O(1)← 正确答案
  • D.缓存命中率更高

答案：C。快排平均 O(n log n) 但最坏退化 O(n²)，归并最坏 O(n log n) 但需要 O(n) 空间；堆排序两者兼得——最坏也是有保证的 O(n log n)，且只需要 O(1) 额外空间。它的劣势是常数因子大、缓存不友好，所以不是“更快”，而是“最坏可预测”。

Q8. 以下哪些场景适合使用堆排序或堆结构？

多选题 · hard

  • A.从 1 亿个数中找出最大的 100 个← 正确答案
  • B.实现优先队列，反复取出最高优先级元素← 正确答案
  • C.对内存极紧张的单片机上的数组排序← 正确答案
  • D.对大型对象数组做稳定排序

答案：ABC。Top-K 问题用大小为 K 的堆扫描全部数据，成本 O(n log K)，A 合适；优先队列的底层就是堆，插入和取最值都是 O(log n)，B 合适；堆排序空间 O(1) 且最坏可控，适合内存紧张场景，C 合适。D 需要稳定排序，堆排序不稳定，更适合归并排序。

Q9. 关于堆排序的时间复杂度，下列说法正确的有？

多选题 · mid

  • A.最好情况是 O(n log n)← 正确答案
  • B.最坏情况是 O(n log n)← 正确答案
  • C.平均情况是 O(n log n)← 正确答案
  • D.最好情况是 O(n)

答案：ABC。堆排序的复杂度不随初始数据分布变化，建堆 O(n)、排序阶段固定 n-1 轮下沉，因此最好、最坏、平均都是 O(n log n)。它不会像快排那样在已有序数组上退化，这是它的稳健性来源。

Q10. 建堆之所以是 O(n) 而不是 O(n log n)，最本质的原因是？

单选题 · extreme

  • A.下沉操作比上浮操作快
  • B.大部分节点位于底层且下沉高度很短，各层工作量求和收敛← 正确答案
  • C.建堆不需要比较元素
  • D.数组随机访问是 O(1)

答案：B。设 h 为从叶层往上数的层号，第 h 层约 n/2^(h+1) 个节点，每个节点最多下沉 h 层，总工作量是 ∑(n/2^(h+1))·h，这个级数收敛于 O(n)。关键在于底层节点数量按指数级增长，但下沉高度按线性缩短，两者对冲后总量是线性。A、C、D 都不是原因。