PriorityQueue (original) (raw)

Louis Wasserman lowasser at google.com
Fri May 15 16:15:56 UTC 2015

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

More information about the core-libs-dev mailing list