Time Complexity of Java PriorityQueue (heap) insertion of n elements?

Question

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

Answer 1

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.