PriorityQueue (original) (raw)

Vitaly Davidovich vitalyd at gmail.com
Fri May 15 14:21:59 UTC 2015

Constructor has advantage in knowing it's working with a clean slate; addAll could check for that too, I suppose, and at least skip things like modCount increments. As a general rule of thumb, I always prefer to have dedicated methods for batch/bulk operations since you have more context to potentially optimize.

sent from my phone On May 15, 2015 10:04 AM, "Chris Hegarty" <chris.hegarty at oracle.com> wrote:

And/Or should PriorityQueue override addAll and provide a more performant implementation for common Collection types ( just like the constructor )?

-Chris. On 15/05/15 14:20, Vitaly Davidovich wrote:

Paul,

I don't think you're missing anything obvious (unless I am as well :)). What you wrote is basically what I meant by creating static helper method in Brett's own code that does exactly what you wrote. The asymptotic complexity will be nlogn in both cases, but the constant factor will be different since addAll() makes iterative add() calls with some overhead (branches, modCount bump, etc). The only O(n) constructors there are one taking SortedSet and copy constructor. Brett did mention he wanted the bulk add functionality (i.e. remove constant factor), and given the class already supports that internally, seems like a harmless change. sent from my phone On May 15, 2015 8:45 AM, "Paul Sandoz" <paul.sandoz at oracle.com> wrote:

On May 14, 2015, at 8:17 AM, Brett Bernstein <brett.bernstein at gmail.com> wrote: I believe the linked sequence of messages refer to the addition of a PriorityQueue constructor only taking a Comparator which was does appear in Java 1.8. Did you have a link to something regarding the a constructor taking a Collection and a Comparator (2 arguments)?

There is an old issue already logged for this: https://bugs.openjdk.java.net/browse/JDK-6356745 Give that one can already do: Collection c = ... Comparator cmp = ... PriorityQueue p =new PriorityQueue(c.size(), cmp); p.addAll(c); Is there a huge need for a new constructor that accepts a collection and a comparator? It seems a nice to have and may be marginally more efficient but AFAICT O-wise addAll and establishing the heap invariant for the entire tree that is initially unordered is the same (unless i am missing something obvious here). Paul.

More information about the core-libs-dev mailing list