On Thu, 14 Dec 2023 20:36:50 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 215: > 213: * Creates a {@code PriorityQueue} containing the elements in the > 214: * specified collection. The {@code PriorityQueue} will order its > 215: * elements according to the specified comparator. The wording "will order its elements" is consistent with the other constructors but I wonder if "its" might be mis-read to mean the collection rather than the queue. If you change it to "will order the priority queue's elements" will avoid that. You'll need to add `@since 23`. Also new tests will need to be added for this constructor. ------------- PR Review Comment: https://git.openjdk.org/jdk/pull/17045#discussion_r1429103333