Menu
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?
876
Answer: Time complexity for the methods offer & poll is O(log(n)) and for the peek() it is Constant time O(1) of java priority queue. SIDE NOTE: In Java programming, Java Priority Queue is implemented using Heap Data Structures, and Heap has O(log(n)) time complexity to insert and delete element.
The time complexity to initialize a PriorityQueue from a collection, even an unsorted one, is O(n). Internally this uses a procedure called siftDown() to "heapify" an array in-place. (This is also called pushdown in the literature.)
A priority queue in Java is a special type of queue wherein all the elements are ordered as per their natural ordering or based on a custom Comparator supplied at the time of creation.
The complexity for remove is O(N) since the complexity for contains is O(N) (in java's priority queue class)
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.
54
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.
24
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
