PriorityQueue
Stuart Marks
stuart.marks at oracle.com
Fri May 15 17:30:42 UTC 2015
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