PriorityQueue

[Vitaly Davidovich]

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