我想从一个自定义比较器的ArrayList中创建一个优先级队列。
public PriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator))
但是在PriorityQueue
中没有这样的构造函数我可以看到这些构造函数，但还没有找到像heapify()那样在O(n)内完成的方法。
- 首先使用构造器创建PQ，然后使用
addAll(...)添加。addAll()将是0 (nlogn)，因为addAll()内部为输入集合的每个元素调用add()。
PriorityQueue<Foo> priorityQueue = new PriorityQueue<>(inputList.size(), comparator);
priorityQueue.addAll(inputList);
- 通过Collection构造函数创建PQ:它没有办法设置比较器
PriorityQueue<Foo> priorityQueue = new PriorityQueue<>(inputList);
一种方法是创建PriorityQueue的子类并添加所需的构造函数。然后在子类中存储集合数组的副本，并重写PriorityQueue#toArray以返回存储的集合数组。最后，使用PriorityQueue(PriorityQueue<> pq)构造PriorityQueue，该构造函数最终将调用PriorityQueue#heapify，后者使用PriorityQueue#siftDown而不是PriorityQueue#siftUp。这将达到您想要的O(N)复杂度。
下面是一个使用构建器类封装(隐藏)PriorityQueue子类的示例实现:
/**
* 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;
}
}
}
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();
}
}
List: 4 8 3 7 10 2 9 5 6 1
PriorityQueue: 1 2 3 4 5 6 7 8 9 10