PriorityQueue (original) (raw)

Chris Hegarty chris.hegarty at oracle.com
Fri May 15 14:04:44 UTC 2015

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