<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">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?<br>
</span></div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div id="Signature">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Cheers,<br>
√</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<b><br>
</b></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<b>Viktor Klang</b></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Software Architect, Java Platform Group<br>
Oracle</div>
</div>
<div id="appendonsend"></div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> core-libs-dev <core-libs-dev-retn@openjdk.org> on behalf of Pavel Rappo <pavel.rappo@oracle.com><br>
<b>Sent:</b> Thursday, 14 December 2023 10:55<br>
<b>To:</b> Valeh Hajiyev <valeh.hajiyev@gmail.com><br>
<b>Cc:</b> core-libs-dev@openjdk.org <core-libs-dev@openjdk.org><br>
<b>Subject:</b> Re: [External] : Re: Introduce constructor for PriorityQueue with existing collection and custom comparator</font>
<div> </div>
</div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt;">
<div class="PlainText">You might want to use this older, unresolved, duplicated bug for your PR:
<a href="https://bugs.openjdk.org/browse/JDK-6356745">https://bugs.openjdk.org/browse/JDK-6356745</a><br>
<br>
> On 13 Dec 2023, at 23:37, Valeh Hajiyev <valeh.hajiyev@gmail.com> wrote:<br>
> <br>
> Hi Pavel,<br>
> <br>
> 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?<br>
> <br>
> Thanks,<br>
> Valeh<br>
> <br>
> On Thu, Dec 14, 2023 at 12:26 AM Pavel Rappo <pavel.rappo@oracle.com> wrote:<br>
> Sorry, there's a necessary process that a PR must follow. You seem to have signed OCA already. For the rest, see this resource:
<a href="https://openjdk.org/guide/">https://openjdk.org/guide/</a>. In particular, this part:
<a href="https://openjdk.org/guide/#contributing-to-an-openjdk-project">https://openjdk.org/guide/#contributing-to-an-openjdk-project</a>.<br>
> <br>
> -Pavel<br>
> <br>
> > On 13 Dec 2023, at 23:09, Valeh Hajiyev <valeh.hajiyev@gmail.com> wrote:<br>
> > <br>
> > Hi all,<br>
> > <br>
> > I have raised the following PR, could someone please help me to get it merged?<br>
> > <br>
> > <a href="https://github.com/openjdk/jdk/pull/17045">https://github.com/openjdk/jdk/pull/17045</a><br>
> > <br>
> > More details:<br>
> > <br>
> > 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)`. <br>
> > <br>
> > ```<br>
> > PriorityQueue<String> pq = new PriorityQueue<>(customComparator);<br>
> > pq.addAll(existingCollection);<br>
> > ```<br>
> > <br>
> > 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.<br>
> > <br>
> > ```<br>
> > PriorityQueue<String> pq = new PriorityQueue<>(existingCollection, customComparator);<br>
> > ```<br>
> > <br>
> > Best regards,<br>
> > Valeh Hajiyev<br>
> > <br>
> <br>
<br>
</div>
</span></font></div>
</body>
</html>