Alex Rivera | Logout

Complexity of PriorityQueue addAll()

Asked 2013-01-14T01:10:57.360
11

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?

java data-structures heap big-o priority-queue
Edit
Report

1 Answer

9

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.

answered 2013-01-14T01:15:44.050

Your Answer