RFR: 6356745: (coll) Add PriorityQueue(Collection, Comparator) [v6]

[Chen Liang]

On Thu, 28 Dec 2023 00:09:09 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:
> 
>   fix style

I think this ticket should focus on adding the new constructor as part of the API.

This constructor can always enjoy the empty-case heapify optimization simply because it is initially empty. It's no fault to mention that.

For previous usages, there is a way to modify `addAll` to heapify if this PQ is empty, but this upgrade can be done in a separate issue, and it does not solve the problem of the lack of constructor parity.

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

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