One approach is to subclass PriorityQueue and add the desired constructor. Then store a copy of the collection's array in the subclass and override PriorityQueue#toArray to return the stored collection's array. Finally, construct a PriorityQueue using the PriorityQueue(PriorityQueue<> pq) constructor which will end up calling PriorityQueue#heapify, which uses PriorityQueue#siftDown rather than PriorityQueue#siftUp. This will achieve the O(N) complexity you want.
Here's an example implementation using a builder class to encapsulate (hide) the PriorityQueue subclass:
/**
* Builder class used to create a {@code PriorityQueue<E>} from a
* {@code Collection<? extends E>} and a {@code Comparator<? super E>} in
* {@code O(N)} time.
*
* @see PriorityQueueBuilder#build(Collection, Comparator)
*/
public final class PriorityQueueBuilder {
/** Don't subclass this class. */
private PriorityQueueBuilder() {}
/**
* Creates a priority queue using a specified collection and comparator in
* {@code O(N)} time.
*
* @param <E> - the priority queue's type
* @param c - the collection to create the priority queue with
* @param comparator - the comparator to be used by the priority queue
* @return a priority queue created from the specified collection and
* comparator
* @throws NullPointerException if the specified collection is {@code null}
*/
public static <E> PriorityQueue<E> build(Collection<? extends E> c, Comparator<? super E> comparator) {
return new PriorityQueue<>(new NPriorityQueue<>(c, comparator));
}
/**
* Temporary priority queue implementation used to create an actual
* {@code PriorityQueue<E>}.
*
* We extend {@code PriorityQueue} in order to use the
* {@code PriorityQueue(PriorityQueue<? extends E> pq)} constructor rather
* than its {@code PriorityQueue(Collection<? extends E> c)} constructor
*/
private static class NPriorityQueue<E> extends PriorityQueue<E> {
private Object[] nQueue;
/**
* Sets the comparator and makes a copy of the collections underlying
* object array.
*/
public NPriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator) {
super(comparator);
nQueue = c.toArray();
}
/**
* Returns an array containing all of the elements in this queue.
* The elements are in no particular order.
*
* We need to override this method in order to return our
* {@code nQueue} rather than {@code PriorityQueue}'s
* {@code queue}. {@code PriorityQueue} calls this method to construct
* the queue in {@code initElementsFromCollection}.
*
* @return an array containing all of the elements in this queue
*/
@Override
public Object[] toArray() {
// no need to return a copy, just pass along the reference
return nQueue;
}
}
}
Here's a class to test the above approach:
public class Driver {
public static final int RANGE_START = 1;
public static final int RANGE_END = 10;
/**
* Entry point of the program.
* @param args - command line arguments
*/
public static void main(String[] args) {
List<Integer> list = IntStream.rangeClosed(RANGE_START, RANGE_END)
.boxed()
.collect(Collectors.toList());
Collections.shuffle(list);
PriorityQueue<Integer> pq = PriorityQueueBuilder.build(list, getComparator());
outputList(list);
outputPriorityQueue(pq);
}
private static Comparator<Integer> getComparator() {
return new Comparator<Integer>()
{
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
}
private static void outputList(List<?> l) {
System.out.print(" List: ");
l.forEach(e -> System.out.printf("%2d ", e));
System.out.println();
}
private static void outputPriorityQueue(PriorityQueue<?> pq) {
System.out.print("PriorityQueue: ");
while (!pq.isEmpty()) {
System.out.printf("%2d ", pq.poll());
}
System.out.println();
}
}
Here's the output of running the test class:
List: 4 8 3 7 10 2 9 5 6 1
PriorityQueue: 1 2 3 4 5 6 7 8 9 10
