-
Enhancement
-
Resolution: Unresolved
-
P4
-
None
-
Cause Known
A DESCRIPTION OF THE REQUEST :
PriorityQueue does not have a constructor that accept a Collection and a Comparator.
JUSTIFICATION :
Most users will users will the next lines
Queue q = new PriorityQueue(comparate);
q.addAll(collection);
The running time for these lines is O(n log n), which defies a motivation to use such a priority queue.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
add the follwing method to the API.
public PriorityQueue( Collection<? extends E> c, Comparator<? super E> comparator);
to achieve an optimal O(n) running time
ACTUAL -
Suboptimal running time
---------- BEGIN SOURCE ----------
Queue q = new PriorityQueue(comparate);
q.addAll(collection);
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
PriorityQueue is not final, but it is not designed (nor documented) for inheritance.
Therefore the only bulletproof work around I found is to create an almost identical class with the same code and an additional constructor.
public PriorityQueueOptimized(Collection<? extends E> collection, Comparator<? super E> comparator) {
this.comparator = comparator;
initializeArray(collection);
fillFromUnsorted(collection);
}
PriorityQueue does not have a constructor that accept a Collection and a Comparator.
JUSTIFICATION :
Most users will users will the next lines
Queue q = new PriorityQueue(comparate);
q.addAll(collection);
The running time for these lines is O(n log n), which defies a motivation to use such a priority queue.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
add the follwing method to the API.
public PriorityQueue( Collection<? extends E> c, Comparator<? super E> comparator);
to achieve an optimal O(n) running time
ACTUAL -
Suboptimal running time
---------- BEGIN SOURCE ----------
Queue q = new PriorityQueue(comparate);
q.addAll(collection);
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
PriorityQueue is not final, but it is not designed (nor documented) for inheritance.
Therefore the only bulletproof work around I found is to create an almost identical class with the same code and an additional constructor.
public PriorityQueueOptimized(Collection<? extends E> collection, Comparator<? super E> comparator) {
this.comparator = comparator;
initializeArray(collection);
fillFromUnsorted(collection);
}
- csr for
-
JDK-8336686 Add PriorityQueue(Collection, Comparator) constructor
-
- Draft
-
- duplicates
-
JDK-8186271 PriorityQueue needs a constructor (Collection, Comparator)
-
- Closed
-
- links to
-
Review(master) openjdk/jdk/17045