Search code examples
javaheapheapsort

Priority List with Heap Sort (Java)

I would like know if exists a Java native implementation for a Priority List using Heap Sort approach. If not, is there any recommended alternative?

Solution

  • The javadoc for PriorityQueue says:

    "An unbounded priority queue based on a priority heap."

    And the source code PriorityQueue for (Java 6 onwards) has this comment:

    "Priority queue represented as a balanced binary heap ..."

    Technically speaking, this is not Heapsort. However, the standard Heapsort algorithm is not appropriate to a priority queue: it is non-incremental (O(NlogN)). What PriorityQueue does is incremental (O(logN) per queue insertion).

    For more details, read the source code. It is well commented.