合并堆作为排序数组实现

Question

当我们有两个二进制最小堆作为双重排序的链接链接实现时，关于最坏情况下将一个堆合并到另一个堆的最有效算法是什么，

我自己的想法是，我将把元素数量较少的堆中的元素插入到元素数量较多的堆中:

如果我可以随机访问元素(这通常不是链表的情况)，它将在O(m * log(n+m))中完成，其中m < n因为我可以将较小堆的每个元素插入到较大堆中，否则它将是O(m * n)，因为我必须将每个元素插入到最小的已经排序的列表中。

有没有其他的方法可以更快地工作，并有更好的最差时间?

Answer 1

您可以在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();
}