优先队列（Java）

概念

优先队列（priority queue）中的元素可以按照任意顺序插入，但会按照有序的顺序检索。不过优先队列并没有对所有元素进行排序，所以迭代处理这些元素，并不需要对它们进行排序。优先队列里面的结构是堆—一个自组织的二叉树，其添加(add)和删除(remove)操作可以让最小元素移动到跟，而不必花时间对元素进行排序

应用场景

任务调度；每一个任务都有一个优先级，任务以随机顺序添加到队列中。每当启动一个新的任务时，都会将优先级最高的任务从队列中删除。

api

java.uti.PriorityQueue

/**
 * 使用默认初始容量（11）创建一个{@code PriorityQueue}，根据元素的{@linkplain Comparable 自然顺序}对其进行排序。
 */
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

/**
 * 使用指定的初始容量创建一个{@code PriorityQueue}，根据元素的{@linkplain Comparable 自然顺序}对其进行排序。
 *
 * @param initialCapacity 该优先队列的初始容量
 * @throws IllegalArgumentException 如果{@code initialCapacity}小于1
 */
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

/**
 * 使用默认初始容量创建一个{@code PriorityQueue}，其中的元素根据指定的比较器进行排序。
 *
 * @param comparator 将用于对此优先队列进行排序的比较器。如果为{@code null}，将使用元素的{@linkplain Comparable 自然顺序}。
 * @since 1.8
 */
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

具体调用比较器比较:

PriorityQueue<pair> pq = new PriorityQueue<>(Comparator.comparingInt(p->p.first));