如何把一个数组建成堆（heapify）？为什么自底向上建堆是 O(n)？

简化版

把无序数组变成堆有两种方式：逐个插入（每个元素上浮，O(n log n)）；自底向上 heapify——从最后一个非叶子节点（下标 n/2-1）开始倒着对每个节点做下沉，O(n)。后者更快，因为大部分节点在底层、下沉高度很小。数学上求和收敛到 O(n)，所以「原地把数组建成堆」是 O(n) 的。

详细版

自底向上建堆（Floyd 建堆法，O(n)）

void buildHeap(int[] a) {
    int n = a.length;
    // 从最后一个非叶子节点开始，倒序下沉
    for (int i = n/2 - 1; i >= 0; i--) {
        siftDown(a, i, n);
    }
}

从 n/2-1 开始：叶子节点没有孩子，不需要下沉，最后一个非叶子节点是 n/2-1。
倒序：保证处理节点 i 时，它的两棵子树已经是堆，才能通过一次下沉把 i 归位。

两种建堆方式对比

方式	做法	复杂度
逐个插入（上浮）	从空堆开始，每加一个元素上浮	O(n log n)
自底向上 heapify（下沉）	从最后一个非叶子节点倒序下沉	O(n)

完整版教学

一、为什么倒序、从非叶子节点开始

自底向上建堆的正确性依赖一个前提：对节点 i 下沉时，它的左右子树必须已经是合法的堆。倒序遍历（从下标大到小）正好保证了这一点——下标大的节点在树的下层，先被处理；轮到上层节点 i 时，它下面的子树早已处理成堆。叶子节点本身就是「单节点堆」，不用处理，所以从最后一个非叶子节点 n/2-1 开始即可。

二、为什么自底向上是 O(n)（关键）

直觉上「n 个节点、每个下沉 O(log n)」应该是 O(n log n)，但实际是 O(n)。原因是下沉的代价和节点所在的高度成正比，而绝大多数节点都在底层、高度很小：

底层（叶子附近）节点最多，但它们下沉高度是 0 或 1。
越往上节点越少，下沉高度才越大。
只有根 1 个节点下沉高度是 log n。

把「每层节点数 × 该层下沉高度」求和：

高度为 h 的节点约有 n/2^(h+1) 个，每个最多下沉 h 步
总代价 = Σ (n/2^(h+1)) × h = n × Σ h/2^(h+1)

而 Σ h/2^h（h 从 0 到 ∞）是一个收敛的级数，收敛到常数 2。所以总代价 = O(n)。核心直觉：多数节点在底层、下沉便宜，少数节点在高层、下沉贵但数量少，加权求和是线性的。

三、为什么逐个插入是 O(n log n)

逐个插入（上浮建堆）正好相反：它是「自顶向下」的思路，每个新元素都可能一路上浮到根。而大部分节点是在堆已经很大时插入的，此时树高已是 log n，上浮代价大。n 个元素每个最坏 O(log n)，总和 O(n log n)。

对比就能看出差异的本质：下沉建堆让”便宜的底层节点”承担了大部分工作量，所以省；上浮建堆让”昂贵的后期插入”占多数，所以贵。 建堆首选自底向上下沉法。

四、走一个例子

数组 [3,1,6,5,2,4]，n=6，从 i=n/2-1=2 倒序下沉：
i=2: 节点6，孩子4 → 6>4 不动
i=1: 节点1，孩子5,2 → 较大5>1，交换 → [3,5,6,1,2,4]
i=0: 节点3，孩子5,6 → 较大6>3，交换 → [6,5,3,1,2,4]
     3 到下标2，孩子4 → 4>3，交换 → [6,5,4,1,2,3]
建成大顶堆 [6,5,4,1,2,3] ✓

五、应用：堆排序的第一步

建堆是堆排序的第一步——先 O(n) 把数组建成大顶堆，再反复取堆顶排序。也用于「一次性给定一批数据、要快速构造优先队列」的场景（比 O(n log n) 逐个插入快）。Java PriorityQueue 的构造函数 new PriorityQueue<>(collection) 内部就是 O(n) 建堆。

六、常见误区与追问

考点	正确口径
自底向上 heapify	从最后一个非叶子节点开始下沉，整体 O(n)
逐个插入建堆	每插入一个元素上浮，整体 O(n log n)
关键直觉	底层节点多但下沉距离短，顶层节点少但下沉距离长

lastNonLeaf = n / 2 - 1
for i from lastNonLeaf downto 0:
  siftDown(i)
sum work <= n/2*1 + n/4*2 + n/8*3 + ... = O(n)

建堆 O(n) 的核心不是每个节点都便宜，而是“节点数量”和“可下沉高度”此消彼长。

误区：heapify 每个节点都下沉 O(log n)，所以总是 O(n log n)。 多数节点在底层，最多下沉 1 到 2 层，不能把每个节点都按根节点的高度估算。
误区：建堆必须从数组头开始。 Floyd 建堆从最后一个非叶子节点倒着处理，因为叶子天然已经是堆。
误区：自底向上建堆和逐个插入没有区别。 逐个插入每次维护一个增长中的堆；heapify 是利用完整数组结构一次性局部修复。
追问：最后一个非叶子节点为什么是 n/2 - 1？ 0 下标数组中，索引大于等于 n/2 的节点没有左孩子，都是叶子。
追问：大顶堆和小顶堆建堆区别是什么？ 框架相同，只是下沉时比较方向不同，大顶堆选更大的孩子，小顶堆选更小的孩子。
追问：heapify 会改变原数组顺序吗？ 会，它原地交换元素来满足堆序，不保持原相对顺序。

七、加强记忆

建堆两法：逐个插入上浮 O(n log n)；自底向上 heapify ——从最后一个非叶子节点 n/2-1 倒序对每个节点下沉，O(n)。倒序是为了下沉时子树已成堆。O(n) 的原因：下沉代价随高度增长，而多数节点在底层、下沉便宜，Σ h/2^h 收敛到常数。建堆首选自底向上下沉法，是堆排序的第一步。

简化版

详细版