Search code examples
javadata-structuresheappriority-queue

How do Java Priority Queues Work Under The Hood?

I cannot seem to find any information to answer my question. So Java PriorityQueue are built using heaps. Heaps have an insertion and deletion time of O(logn) so if I were to do a heap sort that would be O(nlogn).

But during creation of a heap it only takes O(n) time. So lets say I put the line

PriorityQueue<Character> heap = new PriorityQueue<>(list);

Is Java building the data structure with the values so its O(n) or is it inserting afterwards so its O(nlogn)?

Solution

  • You can always check the source: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/PriorityQueue.java

    When you initialize it from an unsorted list, it uses the O(n) heapify method.