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-r...@openjdk.org> on behalf of Pavel Rappo <pavel.ra...@oracle.com> Sent: Thursday, 14 December 2023 10:55 To: Valeh Hajiyev <valeh.haji...@gmail.com> Cc: core-libs-dev@openjdk.org <core-libs-dev@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.haji...@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.ra...@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.haji...@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 > > >
