Complexity PriorityQueue addAll ()

Question

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

Answer 1

Javadoc seems to imply that addAll inherits from AbstractQueue , where it is implemented as a sequence of additions .

This makes me think that the complexity is O(mlogn) , where m is the size of the inserted collection.

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 just what you can assume. Depending on the specific implementation you plan to use, you may find some tricks that can improve the situation for you.

Answer 3

Looking at OpenJDK, it seems that PriorityQueue inherits the addAll implementation from AbstractQueue, which iterates through the collection and causes each element to be added.

A source