Introduce constructor for PriorityQueue with existing collection and custom comparator

Pavel Rappo pavel.rappo at oracle.com
Wed Dec 13 23:25:59 UTC 2023


Sorry, there's a necessary process that a PR must follow. You seem to have signed OCA already. For the rest, see this resource: https://openjdk.org/guide/. In particular, this part: https://openjdk.org/guide/#contributing-to-an-openjdk-project.

-Pavel

> On 13 Dec 2023, at 23:09, Valeh Hajiyev <valeh.hajiyev at gmail.com> wrote:
> 
> Hi all,
> 
> I have raised the following PR, could someone please help me to get it merged?
> 
> https://github.com/openjdk/jdk/pull/17045
> 
> More details:
> 
> 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);
> ```
> 
> Best regards,
> Valeh Hajiyev
> 



More information about the core-libs-dev mailing list