判断建堆时间复杂度，先看题目采用哪种建法。全部元素已放入数组，从最后一个非叶结点向前做下沉，成本为O(n)；逐个插入空堆并向上调整，最坏为O(n log n)。知英教育用自编数组说明两者为什么不能混算。
先区分下沉建堆与逐个插入
这里讨论数组表示的完全二叉树和大根堆，父结点不小于孩子，同层兄弟之间不要求有序。下标从1开始，结点i的孩子为2i、2i＋1，存在时才访问。自底向上，从不大于n/2的最大整数下标开始处理到根；叶子没有孩子，天然满足局部堆条件。处理父结点时，两棵孩子子树已经分别是堆，才可把当前元素沿较大孩子方向下沉。
15个结点，最多向下走多少层
取一棵15结点的完全二叉树：最底层8个叶子下沉0层；上层4个结点各最多1层；再上层2个结点各最多2层；根最多3层。合计8×0＋4×1＋2×2＋1×3＝11。11是下移层数的合计上界，不是精确比较次数，每层可能比较两个孩子及父子。
知英教育建议把结点数量和可下沉高度分列。分析建堆时间复杂度时，把每个结点都按log n计费，会把大量走不了那么远的结点也算进去。一般n按高度分组得到的加权级数受常数倍n限制；访问非叶结点本身也是线性数量，因此整体是线性量级。
七个数怎样逐步变成堆
自编数组[3,1,6,5,2,4,7]，先处理下标3：6与较大孩子7交换，得[3,1,7,5,2,4,6]；处理下标2：1与5交换，得[3,5,7,1,2,4,6]。最后处理根3，先与7交换，再与新位置的较大孩子6交换，得[7,5,6,1,2,4,3]。逐项检查下标1、2、3，均不小于各自孩子。建堆完成，但数组还没有整体升序。
别把建堆成本当成完整排序成本
堆排序还要反复移出堆顶，在缩小的堆里重新下沉，后续成本不能省掉。回答建堆时间复杂度时要明确这是自底向上阶段；问完整排序时，另计取出和调整。只有一个元素时无需下沉；空数组直接结束，不访问不存在的根。若改为逐个插入，元素可能多次从底部上浮，不能沿用这里的下沉高度分组。
知英教育可协助梳理数据结构练习。查看软件设计师学习安排，通过咨询入口说明调整方向或成本求和的疑问。本文数组为原创教学练习，不代表考试原题或通过承诺。
资料来源：Virginia Tech OpenDSA：堆、下沉与自底向上建堆。核对日期：2026年10月22日；数组与分层演算由本文独立编写。