Rippling OA Build Max Heap：自底向上 Heapify 的层序结果

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版使用二叉 max-heap、下标 0 起、sift-down 时两孩子同值优先左孩子；不同同值平局选择可形成不同但都合法的层序数组。
• ‘一次 build-max-heap’指从最后非叶节点到底向上的整轮 Floyd 建堆，不是只在根做一次 sift-down。

解题路线

1. 下标 i≥n//2 都是叶节点，天然满足堆条件；从 n//2−1 到 0 逐个 sift-down，处理 i 时其两个子树已成堆。
2. sift-down 选择更大孩子，若父已≥孩子就停，否则交换并继续沿被换位置下沉；最终根成为该子树最大。
3. 原数组缺失时只给算法和如何核对候选：结果必须是原数组重排、满足父≥子；但这两个条件不足以唯一证明是指定 tie 规则下的 Floyd 输出，需要真正模拟。
4. 建堆总成本 O(n) 而不是 n 个节点各自都 O(log n) 的紧上界：高度 h 的节点数随 h 指数下降，Σ(n/2^{h+1})×h=O(n)。

手动走一遍

数组 [3,1,4,2]：从下标 1 开始，1 与孩子 2 换得 [3,2,4,1]；根 3 与较大孩子 4 换得 [4,2,3,1]。层序就是数组 [4,2,3,1]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def is_max_heap(values: list[int]) -> bool:
    """A flat array already encodes a complete binary tree."""
    return all(values[(child - 1) // 2] >= values[child] for child in range(1, len(values)))


def build_max_heap(values: list[int]) -> list[int]:
    result = values.copy()
    n = len(result)
    for root in range(n // 2 - 1, -1, -1):
        parent = root
        while 2 * parent + 1 < n:
            child = 2 * parent + 1
            if child + 1 < n and result[child + 1] > result[child]:
                child += 1
            if result[parent] >= result[child]:
                break
            result[parent], result[child] = result[child], result[parent]
            parent = child
    return result

复杂度

时间 O(n)、复制训练代码的额外空间 O(n)；若在原数组就地 heapify，辅助空间 O(1)。单次 sift-down 最坏 O(log n)，不能把每个节点最坏直接相加当紧界。

易错点与追问

容易失分的边界

• 只在根做 sift-down，未处理下层子树。
• 把建堆误报为必然 O(n log n)。
• 改变元素多重集或只检查根最大。
• 选项缺失却编出原题最终数组。

继续深挖

• 为什么从最后非叶节点开始？
• 如何证明 O(n) 而非 O(n log n)？
• 同值孩子不同选择对最终数组有什么影响？
• 建好的堆为什么不等于完全排序？