Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the time complexity of constructing a PriorityQueue from a collection?

What is the complexity of Java's PriorityQueue constructor with a Collection? I used the constructor:

PriorityQueue(Collection<? extends E> c)

Is the complexity O(n) or O(n*log(n))?

like image 247
Seffy Golan Avatar asked Jan 09 '16 12:01

Seffy Golan


People also ask

What is the time complexity of PriorityQueue?

To always get the largest element, we use priority queues. The time complexity would be: Creation of priority queue takes O(n) time.

What is the time complexity of the method offer () in the class PriorityQueue?

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.

Is PriorityQueue Min or Max?

The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.

What is the time complexity of removing an item from a priority queue?

It will take O(log N) time to insert and delete each element in the priority queue. Based on heap structure, priority queue also has two types max- priority queue and min - priority queue.


1 Answers

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.)

This is counterintuitive. It seems like inserting an element into a heap is O(log n) so inserting n elements results in O(n log n) complexity. This is true if you insert the elements one at a time. (Internally, inserting an individual element does this using siftUp().)

Heapifying an individual element is certainly O(log n), but the "trick" of siftDown() is that as each element is processed, the number of elements that it has to be sifted past is continually decreasing. So the total complexity isn't n elements times log(n); it's the sum of n terms of the decreasing cost of sifting past the remaining elements.

See this answer, and see also this article that works through the math.

like image 130
Stuart Marks Avatar answered Sep 19 '22 18:09

Stuart Marks