Loading... (original) (raw)

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);
}