From the PriorityQueue Javadoc:
Implementation note: this implementation provides O(log(n)) time for enqueuing and dequeuing methods
offer,poll,remove()andadd; linear time for theremove(Object)andcontains(Object)methods; and constant time for the retrieval methodspeek,element, andsize.
So, my question is, would the O(log(n)) time complexity hold up for merging PriorityQueues into one? Or would it be O(nlog(n)) considering the insertion? And would this change if merging more heaps?
These PriorityQueues are to represent heaps.
Something like this:
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);
As you have pointed out the method add from the class PriorityQueue has O(log(N)) time complexity. If you look at the concrete implementation of the method addAll from the class PriorityQueue, you see the following:
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;
}
So for each element in the collection passed as parameter, the method add is called. Therefore, the finally complexity will be O(Mlog(N)), where M is the number of elements of the collection passed as parameter and N is the number of elements of the priority queue.