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.san...@oracle.com>
wrote:
On May 15, 2015, at 6:15 PM, Louis Wasserman <lowas...@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.
