On Tue, 19 Dec 2023 21:17:02 GMT, Valeh Hajiyev <d...@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
src/java.base/share/classes/java/util/PriorityQueue.java line 216:
> 214: * specified collection. The {@code PriorityQueue} will order the
> 215: * priority queue's elements elements according to the specified
> 216: * comparator.
I know you updated this in response to Alan's comment, but the second sentence
now says "elements elements". And repeating "priority queue" sounds somewhat
redundant. Suggestion for the second sentence:
> The elements of the new {@code PriorityQueue} will be ordered according to
> the specified comparator.
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/17045#discussion_r1432255396
