PriorityQueue

[Louis Wasserman]

http://lcm.csa.iisc.ernet.in/dsa/node139.html suggests an algorithm for
heapifying an unsorted array in O(n), corroborated elsewhere at
http://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf .
Any particular reason we can't use that approach?

On Fri, May 15, 2015 at 7:22 AM Vitaly Davidovich <vitalyd at gmail.com> wrote:

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