如何识别违反Max Heap（最大堆）性质的顶点？求解析Build Heap问题

首先明确最大堆的核心性质：每个父节点的值都大于等于其所有子节点的值。Build Heap的本质就是把无序数组调整为符合该性质的堆结构，核心操作是Max-Heapify（最大堆化）——当某个节点违反最大堆性质时，通过向下交换让它落到正确的位置。

结合你提供的堆化示意图，我们一步步拆解过程：

堆化步骤详解 #

假设初始数组为 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]（对应图中初始层级结构）：

1. 首次调整根节点（值为4）
   根节点4的子树中存在更大的节点16（属于左子树的右节点），违反了最大堆性质。触发Max-Heapify：

   • 先交换4和16的位置，此时原4被移到16的位置（数组索引4）；
   • 新位置的4又发现子节点7比自己大，再次交换，最终该子树满足最大堆性质，数组变为 [16, 1, 3, 2, 7, 9, 10, 14, 8, 4]。

2. 调整左子树的根（值为1）
   节点1的子树中最大的节点是14（左子树的右节点），交换1和14的位置，数组变为 [16, 14, 3, 2, 7, 9, 10, 1, 8, 4]，该子树堆化完成。

3. 调整右子树的根（值为3）
   节点3的子树中最大的节点是10（右子节点），交换3和10的位置，数组变为 [16, 14, 10, 2, 7, 9, 3, 1, 8, 4]，该子树堆化完成。

4. 调整剩余违规节点（值为2）
   节点2的子树中最大的节点是8（右子节点），交换2和8的位置，数组变为 [16, 14, 10, 8, 7, 9, 3, 1, 2, 4]，此时整个堆完全符合最大堆性质，Build Heap操作结束。

核心知识点梳理 #

• Build Heap的时间复杂度为O(n)，而非直觉中的O(nlogn)——因为大部分节点处于堆的底层，堆化时仅需少量层级交换。
• Max-Heapify的前置条件：当前节点的左右子树已经是合法的最大堆，这样只需调整当前节点的位置即可。
• 堆化必须从最后一个非叶子节点开始倒序处理，确保每个节点的子树在处理前已满足堆性质。

内容的提问来源于stack exchange，提问作者vvv-1234