On Tue, 19 Dec 2023 21:17:02 GMT, Valeh Hajiyev <d...@openjdk.org> wrote:
>> 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); > > Valeh Hajiyev has updated the pull request incrementally with one additional > commit since the last revision: > > updated the javadoc Would adding a fast path to addAll solve this issue? I asked this back in 2006 in JDK-6356745. The [TreeMap::putAll](https://github.com/openjdk/jdk/blob/2d609557ffe8e15ab81fb51dce90e40780598371/src/java.base/share/classes/java/util/TreeMap.java#L348) is already implemented to work this way so we could apply the same concept to PriorityQueue and BlockingPriorityQueue For example sake: public boolean addAll(Collection<? extends E> c) { if (c == null) throw new NullPointerException(); if (c == this) throw new IllegalArgumentException(); if (size == 0) { return addAllEmpty(c); } return super.addAll(c); } private boolean addAllEmpty(Collection<? extends E> c) { //assert size == 0 : size; Object[] old = this.queue; try { if (c instanceof SortedSet<?> ss && Objects.equals(this.comparator, ss.comparator()) { initElementsFromCollection(ss); } else if (c instanceof PriorityQueue<?> pq && Objects.equals(this.comparator, pq.comparator())) { initFromPriorityQueue(pq); } else { initFromCollection(c); } } catch (Throwable t) { size = 0; this.queue = old; //super.addAll(c); //Punish the wicked or get rid of all or nothing behavior. throw t; } return size != 0; } This would allow an empty PQ to heapfiy/siftDown. There is a change in that the addAll is all or nothing in the empty case. ------------- PR Comment: https://git.openjdk.org/jdk/pull/17045#issuecomment-1868759233
