PriorityQueue

Paul Sandoz paul.sandoz at oracle.com
Fri May 15 16:40:15 UTC 2015


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