Time complexity (Big-O) of merging two PriorityQueues

user_14743496 0
Viewed 598

From the PriorityQueue Javadoc:

Implementation note: this implementation provides O(log(n)) time for enqueuing and dequeuing methods offer, poll, remove() and add; linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods peek, element, and size.

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);
priority-queue heap big-o time-complexity java
1 Answers

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.

user_13668710
Related