建堆从最后一个非叶子节点（下标n/2−1）开始自底向上下沉调整，时间复杂度为o(n)，因其底层节点调整代价小、高层节点数量少，加权求和收敛于2n；排序阶段为o(n log n)，整体复杂度o(n log n)。
堆排序的建堆过程不是逐个插入，而是从最后一个非叶子节点开始、自底向上进行“下沉调整”（heapify），时间复杂度为 O(n)，而非直觉上的 O(n log n)。这个结果看似反直直觉，但有严谨的数学支撑。
建堆为什么从 n/2 − 1 开始？
因为完全二叉树中，下标从 0 开始的数组里：
- 叶子节点一定位于后半段，即下标范围是
[⌊n/2⌋, n−1] - 最后一个非叶子节点 = 最后一个有子节点的节点 = 索引为
n/2 − 1（向下取整） - 例如数组长度
n = 10，则n/2 − 1 = 4，下标 0~4 是非叶子节点，5~9 是叶子
从该位置倒序遍历到根（索引 0），对每个节点执行一次 heapify，就能确保整个树满足堆性质。
heapify 的本质是“向下调整”
对某个节点 i，比较它与左右子节点（2i+1 和 2i+2），把三者中最大值上浮至 i 位置，若发生交换，则递归或循环地在被换下的子树中继续调整。单次 heapify 最坏耗时为树高，即 O(log n)。
但建堆时，并非所有节点都走满 log n 层——越靠近底层的节点，调整路径越短：
Java JDK 25
下载
Java JDK 25 来自 OpenJDK 官方归档，版本为 JDK 25，本条下载地址已指向官方 Windows x64 zip 安装包直链，适合调试旧项目或兼容旧版 Java 运行环境。
- 约 n/2 个叶子节点：调整代价为 0
- 约 n/4 个深度为 1 的非叶子节点：最多下沉 1 层 → 代价 ≈ 1
- 约 n/8 个深度为 2 的节点：最多下沉 2 层 → 代价 ≈ 2
- ……直到根节点（1 个）：最多下沉 log₂n 层
总代价 ≈ Σ(k=0 to log₂n−1) (n / 2^(k+1)) × k，经等比数列求和可证其收敛于 2n，即 O(n)。
排序阶段的时间复杂度是 O(n log n)
建堆完成后，执行 n−1 轮操作：
- 每次将堆顶（最大值）与当前末尾交换 → O(1)
- 然后对剩余 n−1、n−2、…、2 个元素调用
heapify(0) - 每轮
heapify最坏 O(log size)，size 从 n−1 递减到 1 - 总代价 ≈ log(n−1) + log(n−2) + … + log(1) = log((n−1)!) ≈ n log n（斯特林公式）
因此整体堆排序时间复杂度为 O(n) + O(n log n) = O(n log n)，且最坏、平均、最优情况一致。
为什么不用插入法建堆？
若逐个插入元素并上滤（percolate up），每插入一个需 O(log k)（k 为当前堆大小），总代价为 Σ(log k) ≈ log(n!) = O(n log n)。虽然可行，但不如筛选法高效，也不利于原地实现。工程实践中一律采用自底向上的筛选建堆。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
