PriorityQueue

[Vitaly Davidovich]

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