Details
-
Type:
Enhancement
-
Status: Open
-
Priority:
P4
-
Resolution: Unresolved
-
Affects Version/s: None
-
Fix Version/s: None
-
Component/s: core-libs
-
Subcomponent:
-
Understanding:Cause Known
Description
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);
}
Attachments
Issue Links
- duplicates
-
JDK-8186271 PriorityQueue needs a constructor (Collection, Comparator)
-
- Closed
-