Introduce constructor for PriorityQueue with existing collection and custom comparator

David Holmes david.holmes at oracle.com
Thu Dec 14 08:16:07 UTC 2023


The current mailing list, core-libs-dev, is the correct one.

Cheers,
David

On 14/12/2023 9:37 am, Valeh Hajiyev wrote:
> Hi Pavel,
> 
> Thanks for the reply. If I understand correctly, I need this change to 
> be discussed in one of the mailing lists there, so that someone would 
> sponsor me to create a tracking issue in JBS. Do you know which mailing 
> list is the most relevant for me to propose the change?
> 
> Thanks,
> Valeh
> 
> On Thu, Dec 14, 2023 at 12:26 AM Pavel Rappo <pavel.rappo at oracle.com 
> <mailto:pavel.rappo at oracle.com>> wrote:
> 
>     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/ <https://openjdk.org/guide/>. In
>     particular, this part:
>     https://openjdk.org/guide/#contributing-to-an-openjdk-project
>     <https://openjdk.org/guide/#contributing-to-an-openjdk-project>.
> 
>     -Pavel
> 
>      > On 13 Dec 2023, at 23:09, Valeh Hajiyev <valeh.hajiyev at gmail.com
>     <mailto: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
>     <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