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);
    }
Posted Date : 2005-11-30 00:56:01.0

N/A

The suggested addition is consistent with existing APIs
in the collection classes.
Posted Date : 2005-11-30 05:58:50.0

An SDN member quite reasonably suggests,

"Why not just make a fast path for the addAll method and avoid the API change?  
The TreeMap putAll method works that way."
Posted Date : 2006-03-03 20:53:47.0

There's something being missed here.
The only way initializing a PriorityQueue from another collection
could be O(N) is if the elements in the other collection are
already sorted into the desired order.
Any method or constructor taking an arbitrary collection and comparator
must be O(N*LOG(N)) to maintain the heap invariant.
Posted Date : 2006-03-05 17:41:58.0

Why not just make a fast path for the addAll method and avoid the API change?  The TreeMap putAll method works that way. 

Another issue with the current copy constructor is it allows null to be injected in to the PriorityQueue.  A rare case but, it seems that the safest way to add items is O(N*LOG(N)).


import java.util.*;

public class QueueTest {
    public static void main(String[] args) {
        test(fill(new TreeSet<Comparable>(Nulls.HIGH)));
        test(fill(new TreeSet<Comparable>(Nulls.LOW)));
        test(fill(new ArrayList<Comparable>()));
    }
    
    private static void test(Collection<Comparable> c) {
        try {
            PriorityQueue pq = new PriorityQueue(c);
            final Object[] a = pq.toArray();
            if(Arrays.asList(a).contains(null))
                if(!pq.contains(null))
                    System.out.println("Fail. "+ c.getClass().getName());
                else
                    System.out.println("Pass.");
            else
                assert false;
        }
        catch(final NullPointerException NPE) {
            System.out.println("Pass. PQ threw a "+ NPE.getClass().getName());
            //NPE.printStackTrace(System.out);
        }
    }
    
    private static Collection<Comparable> fill(Collection<Comparable> c) {
        c.add(1);
        c.add(null);
        c.add(2);
        return c;
    }
    
    private static class Nulls implements Comparator<Comparable> {
        private static final Nulls HIGH = new Nulls(1);
        private static final Nulls LOW = new Nulls(-1);
        
        private final int modifier;
        
        private Nulls(final int modifier) { this.modifier = modifier; }
        
        public int compare(Comparable o1, Comparable o2) {
            if(o1 != null &&  o2 != null)
                return o1.compareTo(o2);
            if(o1 == null)
                return -1 * modifier;
            return 1 * modifier;
        }
    } 
}

/*
Fail. java.util.TreeSet
Fail. java.util.TreeSet
Pass. PQ threw a java.lang.NullPointerException
*/