[External] : Re: Introduce constructor for PriorityQueue with existing collection and custom comparator

[Viktor Klang]

I presume that the precondition to have the original collection be pre-ordered according to the supplied Comparator can be verified by checking before adding each element in the collection to the PQ that it compareTo equal-or-greater to the previous one?


Cheers,
√


Viktor Klang
Software Architect, Java Platform Group
Oracle
________________________________
From: core-libs-dev <core-libs-dev-retn at openjdk.org> on behalf of Pavel Rappo <pavel.rappo at oracle.com>
Sent: Thursday, 14 December 2023 10:55
To: Valeh Hajiyev <valeh.hajiyev at gmail.com>
Cc: core-libs-dev at openjdk.org <core-libs-dev at openjdk.org>
Subject: Re: [External] : Re: Introduce constructor for PriorityQueue with existing collection and custom comparator

You might want to use this older, unresolved, duplicated bug for your PR: https://bugs.openjdk.org/browse/JDK-6356745

> On 13 Dec 2023, at 23:37, Valeh Hajiyev <valeh.hajiyev at gmail.com> 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> 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/. 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
> >
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20231214/5c156fa8/attachment-0001.htm>