algorithm - 合并实现为排序数组的堆

当我们将两个二进制最小堆实现为双排序链接时，关于将一个堆合并到另一个堆的最坏情况时间，最有效的算法是什么？
我自己认为，我会将具有较少元素的堆元素插入具有较多元素的堆中：
如果我有对元素的随机访问权（通常不是链表的情况），则可以在O(m * log(n+m))中完成，因为我可以将较小堆中的每个元素插入到较大堆中，否则将在m < n中完成，因为我必须将每个元素插入到已排序列表的最小值中。
有没有其他的方法可以更快的工作，更好的度过最糟糕的时刻？

最佳答案

您可以在O（m+n）时间内轻松完成此操作，只要您能够跟踪在堆遍历中检查的节点在伪代码中：

Iterator iterDest = largerHeap.getIterator();
Iterator iterSrc = smallerHeap.getIterator();

while (iterSrc.hasMore()) {
    valueSrc = iterSrc.getCurrent();
    valueDest = iterDest.getCurrent();

    if (valueSrc <= valueDest) {
        // Insert elements in their proper place in largerHeap
        iterDest.insertBeforeCurrent(valueSrc);
        iterSrc.moveNext();
    } else {
        if (iterDest.hasMore()) {
            iterDest.moveNext();
        } else {
            break;
        }
    }
}

// Append extra elements to the end of largerHeap
while (iterSrc.hasMore()) {
    largerHeap.append(iterSrc.getCurrent());
    iterSrc.moveNext();
}