PriorityQueue (original) (raw)

Vitaly Davidovich vitalyd at gmail.com
Fri May 15 17:47:49 UTC 2015

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 <stuart.marks at oracle.com> 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 <paul.sandoz at oracle.com> wrote:

On May 15, 2015, at 6:15 PM, Louis Wasserman <lowasser at google.com> 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.

More information about the core-libs-dev mailing list