两个binary min-heap（二叉最小堆）合并为2n大小堆的低复杂度方案咨询

前置说明 #

普通数组存储的隐式完全二叉最小堆，不存在理论上严格O(log n)时间、O(1)额外空间的合并方案，工业界最常用的原地合并方案时间复杂度为O(n)，仅需常数级额外空间。如果你的堆采用链式存储且提前维护了尾节点指针，可以实现严格O(log n)时间、O(1)额外空间的合并，两种方案如下： #

方案1：数组式隐式堆原地合并（最常用，O(n)时间、O(1)额外空间） #

该方案基于标准层序存储的数组堆实现，步骤如下：

• 直接将第二个堆的所有元素按原顺序追加到第一个堆的数组末尾，此时数组总长度恰好为2n，满足大小要求
• 定位到完全二叉树的最后一个非叶子节点，下标为 (2n // 2) - 1（0索引数组）
• 从该节点开始从后往前遍历所有非叶子节点，对每个节点执行min_heapify（最小堆下沉调整）操作，遍历完成后即可得到合法的2n大小二叉最小堆

该方案的时间复杂度符合二叉堆建堆的理论下界O(n)，全程仅使用循环下标、临时变量等常数级额外空间，满足O(1)空间要求
核心调整函数伪代码示例：

def min_heapify(arr: list, heap_size: int, idx: int) -> None:
    smallest = idx
    left_child = 2 * idx + 1
    right_child = 2 * idx + 2
    # 找当前节点、左右孩子中最小值的下标
    if left_child < heap_size and arr[left_child] < arr[smallest]:
        smallest = left_child
    if right_child < heap_size and arr[right_child] < arr[smallest]:
        smallest = right_child
    # 最小值不是当前节点则交换，继续下沉调整
    if smallest != idx:
        arr[idx], arr[smallest] = arr[smallest], arr[idx]
        min_heapify(arr, heap_size, smallest)

方案2：链式存储二叉堆合并（O(log n)时间、O(1)额外空间） #

如果你的堆采用链式存储（每个节点存左孩子、右孩子、父节点指针，且提前维护了堆的尾节点指针，即完全二叉树的最后一个节点），可以按如下步骤实现：

• 比较两个堆的根节点值，将根值更大的堆整体作为子节点，插入到根值更小的堆的尾节点下，维持完全二叉树的结构
• 将插入的大堆根节点作为当前节点，执行向上调整（bubble_up）操作：不断和父节点比较，若当前节点值更小则交换，直到父节点值更小或到达根节点
• 调整完成后更新整个堆的尾节点指针即可

该方案仅需要最多O(log 2n)次节点比较和交换操作，时间复杂度为O(log n)，全程仅使用常数个指针临时变量，满足O(1)空间要求。注意如果没有提前维护尾节点指针，查找尾节点需要O(n)时间，无法达到O(log n)的时间要求

内容的提问来源于stack exchange，提问作者bennietgek