algorithm - 给定两个每个大小为 n 的最大堆，从两个最大堆的元素中生成一个最大堆的最小可能时间复杂度是多少？

Question

给定两个每个大小为 n 的最大堆，从两个最大堆的元素中生成一个最大堆的最小可能时间复杂度是多少？

我已经阅读了几个答案，每个人都说 O(n) 是这个问题的答案，因为我们可以将两个堆中的所有元素放入一个大小为 2n 的数组中，然后运行一个构建堆算法，该算法需要O(n) 时间复杂度。

但是考虑一下，这种方法:

1. 从两个堆中取出最后一个元素并确定哪个最小，并将其作为新堆的根 [O(1)]
2. 将旧堆作为新根的子堆。
3. 在这个新堆上运行最大堆化算法 [ O(logn) ]

总 T = O(1+logn) = O(logn)

我知道节点 X 上的 max heapify 假定 X 下面的节点已经是最大堆(这在我上面所说的过程中已经得到满足，因为两个旧堆本身都是最大堆。)

我哪里错了？

Answer 1

(我假设您的堆模型是二叉树，而不是数组)。

堆的一个特性是底层从左到右没有间隙地填充。当您有两个大小为 n 的堆时，它们的底部层已部分填充，因此您无法方便地将它们连接成一个更大的堆。

你的证明中的错误是 max heapify 要求树的底层节点从左到右填充。

请注意，没有任何方便的方法可以使您的想法适用于一般情况。这是因为每个堆的底层可能有 1 到 n/2 个节点，因此您需要接触 O(n) 个节点来构建堆。