java - 合并两个不同大小的堆

Question

这是一个有点家庭作业的问题，有点不是。在我的作业中，我必须演示如何合并两个相同大小的堆并估计它的时间复杂度。当我在寻找这个时，我读到了倾斜堆和斐波那契堆。

我的问题是，你能把两个不同大小的堆合并成一个堆吗？对于我在网上找到的所有示例，我无法从中得到直接的答案。

感谢大家。

Answer 1

取一个大小为 M+N 的数组：其中 M 是第一个数组的大小，N 是第二个数组的大小。现在将所有元素插入该数组并对其进行 hepify。时间复杂度将是 O((m+n)log(m+n)){因为每个 hepify 操作需要 log(m+n) 并且我们有 m+n 个元素} +插入操作的复杂度：Theta(m) +Theta(n) + O((m+n)log(m+n))