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