合并两个优先级队列的时间复杂度(Big-O)

Question

从优先级队列Javadoc:

实施说明：此实施提供O(log(n((排队和出队方法的时间offer、poll、remove()和add；remove(Object)和contains(Object)的线性时间方法；以及检索方法的恒定时间peek、element和size。

所以，我的问题是，O(log(n((时间复杂性是否能支持将PriorityQueue合并为一？或者考虑到插入，它会是O(nlog(n((吗？如果合并更多的堆，这种情况会改变吗？

这些PriorityQueue表示堆。

类似这样的东西：

PriortityQueue<Integer> a = new PriorityQueue<>();
... add elements
PriortityQueue<Integer> b = new PriorityQueue<>();
... add elements
PriorityQueue<Integer> merged = new PriorityQueue<>(a.size() + b.size(), a.comparator()); // Assuming a and b have the same Comparator.
merged.addAll(a);
merged.addAll(b);

Answer 1

正如您所指出的，类PriorityQueue中的方法add具有O(log(N))的时间复杂性。如果您查看PriorityQueue类中方法addAll的具体实现，您会看到以下内容：

public boolean addAll(Collection<? extends E> c) {
if (c == null)
throw new NullPointerException();
if (c == this)
throw new IllegalArgumentException();
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}

因此，对于作为参数传递的集合中的每个元素，都会调用方法add。因此，最后的复杂度将是O(Mlog(N))，其中M是作为参数传递的集合的元素数量，N是优先级队列的元素数量。