> > I was initially confused by this because it seems to attribute the > algorithmic difference to Comparable vs Comparator, which doesn't make any > sense
That's exactly what threw me off as well, but I didn't bother checking (doh!). Anyway, I think the upside is we're all in agreement now that this is *definitely* a worthwhile improvement :). On Fri, May 15, 2015 at 1:30 PM, Stuart Marks <[email protected]> wrote: > Yes, this is very subtle, and Brett mentioned it (albeit somewhat > obliquely) in an email on jdk9-dev: [1] > > If someone needs to make a >> heap and their data is Comparable, the corresponding constructor gives a >> O(n) runtime. If their data uses a Comparator, the corresponding runtime >> (using addAll) is O(n*log(n)). >> > > I was initially confused by this because it seems to attribute the > algorithmic difference to Comparable vs Comparator, which doesn't make any > sense. (I managed to unconfuse myself before opening my big mouth, though.) > The real issue is that the Collection-consuming constructor code path goes > through heapify() and siftDown(), whereas the non-Collection-consuming > constructor followed by addAll() goes through siftUp(). > > The problem is that if you want your own Comparator, there's no > constructor that takes a Collection, so you're forced to the slow path. > > Earlier in this thread, Paul unearthed JDK-6356745 [2] which says > essentially the same thing as proposed here. I'll update it with some notes. > > > s'marks > > > [1] http://mail.openjdk.java.net/pipermail/jdk9-dev/2015-May/002205.html > > [2] https://bugs.openjdk.java.net/browse/JDK-6356745 > > > > > On 5/15/15 9:45 AM, Vitaly Davidovich wrote: > >> Whoops, I believe you're right -- I completely overlooked that as well :( >> >> On Fri, May 15, 2015 at 12:40 PM, Paul Sandoz <[email protected]> >> wrote: >> >> >>> On May 15, 2015, at 6:15 PM, Louis Wasserman <[email protected]> >>> wrote: >>> >>> 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? >>>> >>>> >>> Thanks. I got things wrong before. I believe the PQ.heapify() does >>> exactly >>> that: >>> >>> private void heapify() { >>> for (int i = (size >>> 1) - 1; i >= 0; i--) >>> siftDown(i, (E) queue[i]); >>> } >>> >>> So there is more value in the constructor than i originally thought. >>> >>> Paul. >>> >>>
