Summary

Add a new constructor to PriorityQueue that takes a Collection and a Comparator.

Problem

Creating a PriorityQueue with an existing Collection and a custom Comparator is inefficient; it can use heapify which is O(N) in time complexity, but it currently has to be done via addAll, which has O(N log N) time complexity. Calling

var a = new PriorityQueue<>(cmp);
a.addAll(coll);
// use a

is way less concise compared to new PriorityQueue<>(coll, cmp).

Solution

Add a new constructor PriorityQueue(Collection, Comparator) to explicitly allow the heapify process when a custom comparator is given. This constructor would be in pair with PriorityQueue(Collection), as all other PriorityQueue constructors come in natural-order and comparator pairs (() and (Comparator), (int) and (int, Comparator) ones)

An alternative solution would be to override addAll(Collection) to call initFromCollection when the PriorityQueue is empty. This would have the same effect as the new constructor and is applicable to all empty PriorityQueues, but doesn't solve the parity issue mentioned above.

Many other collections, such as PriorityBlockingQueue, TreeSet, TreeMap etc. suffers from the same shortcoming. We anticipate to add similar constructors to these collection APIs as well.

Specification

--- a/src/java.base/share/classes/java/util/PriorityQueue.java
+++ b/src/java.base/share/classes/java/util/PriorityQueue.java
@@ -209,6 +209,25 @@ else if (c instanceof PriorityQueue<?>) {
         }
     }

+    /**
+     * Creates a {@code PriorityQueue} containing the elements in the
+     * specified collection. The {@code PriorityQueue} will order its
+     * elements according to the specified comparator.
+     *
+     * @param  c the collection whose elements are to be placed
+     *         into this priority queue
+     * @param  comparator the comparator that will be used to order this
+     *         priority queue.  If {@code null}, the {@linkplain Comparable
+     *         natural ordering} of the elements will be used.
+     * @throws NullPointerException if the specified collection or any
+     *         of its elements are null
+     * @since 24
+     */
+    public PriorityQueue(Collection<? extends E> c,
+                         Comparator<? super E> comparator) {
+        this.comparator = comparator;
+        initFromCollection(c);
+    }
+
     /**
      * Creates a {@code PriorityQueue} containing the elements in the
      * specified priority queue.  This priority queue will be