Complexity of PriorityQueue addAll()

Question

What is the complexity of the addAll method of PriorityQueue. Does it add one element at a time resulting in O(n log n) or does it use a build heap process that creates a heap out of unordered elements in O(n) time?

Astroid

Answer 1

Javadoc seems to imply that addAll is inherited from AbstractQueue where it is implemented as a sequence of adds.

This leads me to believe that the complexity is O(mlogn) where m is the size of the collection being inserted.

Julio

...? O(m log n), not O(m n log n). – Luthuli

I think it would be O(m log(n+m)). Think about case when n=0 – Veridical

Answer 2

From Priority Queue

... this implementation provides O(log(n)) time for the enqueing and dequeing methods ...

So you can only assume n log(n).

However - obviously - this is only what you can assume. Depending on the specific implementation you plan to use you may find some tricks that could improve matters for you.

Lout

Answer 3

Looking at the OpenJDK, it looks like PriorityQueue inherits the addAll implementation from AbstractQueue which iterates over the collection and calls add on each element.

Source

Keturahkeung

Answer 4

The addAll method in PriorityQueue implements add method for every element. Hence it has the time complexity of nlogn.

But this doesn't mean there is nothing equivalent to python's heapq.heapify() or C++ make_heap method that run in O(n) complexity. The PriorityQueue has the constructor that does the heapify operation with O(n) complexity.

List<Integer> x = Arrays.asList(1, 54, 22, 87, 242, 32, 11, 90);
PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(x); // O(n) complexity

PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>();
pq2.addAll(x); // nlogn complexity

Colossal

That is true, but then it uses natural ordering (so min heap for Ints). Is there a way to run heapify with a custom comparator? – Broglie