19

I would like to know what the time complexity of Java PriorityQueue.Add() is for n elements.

I understand that potential worse case insertion a single element is O(log(n)), but it is not clear to me what the time complexity is for inserting a collection of n elements?

I've seen claims from various sources (with no proofs) that the time to build a priority queue heap of n elements it is O(n), and have also seen claims that it is O(nlog(n)), which makes sense given insertion is O(log(n)), which multiplied n times would indeed equal O(nlog(n))

Note: I'm only interested in worse case, not amortized.

This question assumes there is a logical way to describe the act of populating a data structure (heap) with n elements, that is different than simply considering n x log(n) insertions individually.

I'm making no assumptions regarding the input (such as a bounds on the set of input values, or a partially ordered input).

James Wierzba
  • 16,176
  • 14
  • 79
  • 120
  • the guy below is playing on your wrong definition. with the time complexity of inserting into data structures usually means that if you have n elements in the structure, what is the time complexity of inserting 1 element into it. you said inserting n elements. you can't insert less than n if you want to insert n. – MarianP Nov 21 '17 at 20:39
  • @MarianP Is there no standard logical way to describe the act of "populating" a data structure with `n` elements? It is a fairly common scenario. – James Wierzba Nov 21 '17 at 22:05
  • @pjs yes you are right, that is a duplicate. I will add my vote to close and point to existing question – James Wierzba Nov 21 '17 at 23:34

2 Answers2

23

It seems like the insertion of n elements should be O(n log n)

Java PriorityQueue (Java Doc)

O(log n) time for the enqueing and dequeing methods (offer, poll, remove() and add)

O(n) for the remove(Object) and contains(Object) methods

O(1) for the retrieval methods (peek, element, and size)

These time complexities seem all worst case (wiki), except for .add(). You are right to question the bounds as the Java Doc also states to the extension of this unbound structure:

The details of the growth policy are not specified

As they state in the Doc as well, the PriorityQueue is based on an array with a specific initial capacity. I would assume that the growth will cost O(n) time, which then would also be the worst case time complexity for .add().

To get a guaranteed O(n log n) time for adding n elements you may state the size of your n elements to omit extension of the container:

PriorityQueue(int initialCapacity)

EDIT: To the claim of O(n) time for construction is correct (as stated by @pjs in the comments). This procedure is often called heapify and works on an pre existing array that is used to construct a binary tree on it in O(n) time.

gue
  • 1,868
  • 1
  • 16
  • 21
  • 3
    Sorry, but your intuition (and therefore your answer) is wrong about building a heap. I've flagged this as a duplicate, you can find the correct answer along with multiple links to sources and proofs there. – pjs Nov 21 '17 at 23:35
  • 4
    Thank you for your feedback, I modified that part of my answer. I do not find this as a duplicate as the question is related to the .add() method of a specific Java container and not about the construction of a general heap. – gue Nov 22 '17 at 00:02
11

It is O(N log N) in the general case. An O(N) algorithm exists for the special case where the input is already ordered, but this isn't provided in java.util.PriorityQueue.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • Interestingly there are more elaborate methods to sort in linear time assuming the input is of a specific type, some are mentioned in this post: https://stackoverflow.com/questions/749585/sorting-in-linear-time – gue Nov 21 '17 at 22:33
  • @gue Oh yeah. For example if the input is already in the correct PQ order it is just `pq.a[i++] = input.nextElement()`. – user207421 Nov 21 '17 at 23:13
  • 2
    Pre-sorted data is not required, there's a Theta(n) algorithm that works with any set of data. See the linked answer. – pjs Nov 21 '17 at 23:37
  • How about: log 1, log 2... log N for inserting 1st, 2nd, .... Nth element? log 1 + log 2 + ... + log N = log N! – Vyshnav Ramesh Thrissur Mar 07 '21 at 10:42