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" <[email protected]> wrote:
On May 14, 2015, at 8:17 AM, Brett Bernstein <[email protected]>
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.
