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

Valeh Hajiyev duke at openjdk.org
Tue Dec 19 21:17:02 UTC 2023


> 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

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

Changes:
  - all: https://git.openjdk.org/jdk/pull/17045/files
  - new: https://git.openjdk.org/jdk/pull/17045/files/04811c98..6884929b

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=17045&range=03
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=17045&range=02-03

  Stats: 3 lines in 1 file changed: 1 ins; 0 del; 2 mod
  Patch: https://git.openjdk.org/jdk/pull/17045.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/17045/head:pull/17045

PR: https://git.openjdk.org/jdk/pull/17045


More information about the core-libs-dev mailing list