RFR: 6356745: Introduce constructor for PriorityQueue with existing collection and custom comparator [v2]

[Chen Liang]

On Thu, 14 Dec 2023 20:36:50 GMT, Valeh Hajiyev <duke at openjdk.org> wrote:

>> This commit addresses the current limitation in the `PriorityQueue` implementation, which lacks a constructor to efficiently create a priority queue with a custom comparator and an existing collection. In order to create such a queue, we currently need to initialize a new queue with custom comparator, and after that populate the queue using `addAll()` method, which in the background calls `add()` method (which takes `O(logn)` time) for each element of the collection (`n` times).  This is resulting in an overall time complexity of `O(nlogn)`. 
>> 
>> 
>> PriorityQueue<String> pq = new PriorityQueue<>(customComparator);
>> pq.addAll(existingCollection);
>> 
>> 
>> The pull request introduces a new constructor to streamline this process and reduce the time complexity to `O(n)`.  If you create the queue above using the new constructor, the contents of the collection will be copied (which takes `O(n)` time) and then later  `heapify()` operation (Floyd's algorithm) will be called once (another `O(n)` time). Overall the operation will be reduced from `O(nlogn)` to `O(2n)` -> `O(n)` time.
>> 
>> 
>> PriorityQueue<String> pq = new PriorityQueue<>(existingCollection, customComparator);
>
> Valeh Hajiyev has updated the pull request incrementally with one additional commit since the last revision:
> 
>   updated the javadoc

You should update the GitHub PR title to `6356745: (coll) Add PriorityQueue(Collection, Comparator)` to match the JBS issue title.

In addition, you will need a [CSR](https://wiki.openjdk.org/display/csr) as the bot tells you. Its prompt is like:

Summary
A concise description of the proposed change. The description should be one to two sentences long and written to be reusable in documents aggregating changes for a release.

Problem
A brief description of the problem, optionally including the motivation for developing a solution.

Solution
An overview of the solution. Alternative solutions may be discussed; links to rationale documents or review threads welcome to provide additional background to reviewers.

Specification
The detailed changes. Acceptable normative formats include inline patches, attached webrevs, and attached specdiffs. The names of attached files are recommended to include a bug id. References to external webservers, such as http://cr.openjdk.java.net/, can be provided as informative supplements for the convenience of reviewers, but must be accompanied by a normative form of the specification directly associated with the CSR issue to satisfy archival purposes.


I can create one for you, and here's my proposed CSR content:

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.

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.

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 23
    +     */
    +    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


Also extra fields:
 - Scope: SE
 - Compatibility Risk: Minimal
 - Compatibility Risk Description: Adding a new constructor to an existing class is a compatible change.

You can upload the CSR content you propose in the comments, and I will create a CSR for you.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/17045#issuecomment-1859200431