title: Time Complexity of Java PriorityQueue (heap) insertion of n elements?
body: <p>I would like to know what the time complexity of Java <code>PriorityQueue.Add()</code> is for <code>n</code> elements. </p>
  
  <p>I understand that potential worse case insertion a single element is <code>O(log(n))</code>, but it is not clear to me what the time complexity is for inserting a collection of <code>n</code> elements? </p>
  
  <p>I've seen claims from various sources (with no proofs) that the time to build a priority queue heap of <code>n</code> elements it is <code>O(n)</code>, and have also seen claims that it is <code>O(nlog(n))</code>, which makes sense given insertion is <code>O(log(n))</code>, which multiplied <code>n</code> times would indeed equal <code>O(nlog(n))</code></p>
  
  <p>Note: I'm only interested in worse case, not amortized.</p>
  
  <p>This question assumes there is a logical way to describe the act of populating a data structure (heap) with <code>n</code> elements, that is different than simply considering <code>n</code> x <code>log(n)</code> insertions individually.</p>
  
  <p>I'm making no assumptions regarding the input (such as a bounds on the set of input values, or a partially ordered input).</p>