核心特性

类结构

public class PriorityQueue<E> extends AbstractQueue<E>
        implements java.io.Serializable {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    // 存储堆元素的数组，下标 0 是堆顶
    transient Object[] queue;

    // 元素个数（注意：size 与 queue.length 含义不同）
    int size;

    // 自定义比较器；为 null 时使用元素的自然顺序（Comparable）
    private final Comparator<? super E> comparator;

    // 结构性修改次数，用于迭代器 fail-fast
    transient int modCount;
    ...
}

二叉堆结构

// 示例：向队列中依次加入 3, 1, 2，堆顶始终是最小的 1
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
pq.peek();   // 1
pq.poll();   // 1（取出后堆自动调整，peek 变为 2）

构造方法与初始化

// 用集合初始化：直接复制数组后原地建堆，复杂度 O(n)
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?> sortedSet) {
        this.comparator = (Comparator<? super E>) sortedSet.comparator();
        initElementsFromCollection(sortedSet);
    } else if (c instanceof PriorityQueue<?> pq) {
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    } else {
        this.comparator = null;
        initFromCollection(c);
    }
}

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}

private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1;   // 从最后一个非叶子节点开始
    if (comparator == null)
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i]);
    else
        for (; i >= 0; i--)
            siftDownUsingComparator(i, (E) es[i]);
}

核心操作：offer/add（插入）

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();       // 不允许 null
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);                            // 扩容
    siftUp(i, e);                               // 放在末尾，向上调整
    size = i + 1;
    return true;
}

siftUp 源码（默认比较器）

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;      // 父节点下标
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)   // 新元素 >= 父节点，堆性质已满足
            break;
        queue[k] = e;                    // 父节点下沉（只搬元素，不交换）
        k = parent;
    }
    queue[k] = key;                      // 找到最终位置
}

核心操作：poll（取出堆顶）

public E poll() {
    final Object[] es;
    final E result;
    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];  // 最后一个元素
        es[n] = null;                       // 置空，帮助 GC
        if (n > 0)
            siftDown(0, x);                 // 用最后一个元素填补堆顶，向下调整
    }
    return result;
}

siftDown 源码（默认比较器）

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    int half = size >>> 1;                 // 非叶子节点的下标范围是 [0, half)
    while (k < half) {                     // 有左子节点才需要继续下沉
        int child = (k << 1) + 1;          // 左子节点
        int right = child + 1;             // 右子节点
        Object c = queue[child];
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];      // 取左右子节点中较小者
        if (key.compareTo((E) c) <= 0)     // 当前元素 <= 子节点中较小者，停止
            break;
        queue[k] = c;                      // 较小的子节点上移
        k = child;
    }
    queue[k] = key;
}

核心操作：remove(Object)

public boolean remove(Object o) {
    int i = indexOf(o);          // 线性遍历查找下标，O(n)
    if (i == -1)
        return false;
    modCount++;
    int s = --size;
    if (s == i)                  // 删除的就是最后一个元素，直接置空
        queue[i] = null;
    else {
        E moved = (E) queue[s];  // 最后一个元素
        queue[s] = null;
        siftDown(i, moved);      // 先尝试下沉
        if (queue[i] == moved) { // 没下沉（moved 仍在原位），说明 moved 小于子树，需要上浮
            siftUp(i, moved);
        }
    }
    return true;
}

扩容机制：grow

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 容量小于 64 时翻倍再加 2；否则扩容 1.5 倍
    int newCapacity = oldCapacity + ((oldCapacity < 64)
                                     ? (oldCapacity + 2)
                                     : (oldCapacity >> 1));
    // 溢出保护
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

peek

public E peek() {
    return (E) queue[0];   // 直接返回堆顶，O(1)，不调整
}

迭代器与 fail-fast

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(3, 1, 2));
// 迭代输出：3, 1, 2（数组顺序）
for (Integer i : pq) System.out.print(i + " ");  // 3 1 2
// 依次 poll 输出：1, 2, 3（堆序）
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");  // 1 2 3

使用场景与示例

1. Top-K（求最大/最小的 K 个元素）

// 求数据流中最大的 3 个数：用小顶堆（堆顶是最小值，超过 K 就淘汰堆顶）
PriorityQueue<Integer> topK = new PriorityQueue<>(3);
for (int num : new int[]{5, 3, 9, 1, 7, 6}) {
    topK.offer(num);
    if (topK.size() > 3) topK.poll();
}
System.out.println(topK);  // [6, 7, 9]（数组顺序，非堆序）

2. 大顶堆（通过 Comparator 反转）

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(1); maxHeap.offer(5); maxHeap.offer(3);
maxHeap.peek();  // 5

3. 按对象字段排序

// 按任务截止时间排序（最早截止的最先处理）
PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingLong(Task::getDeadline));

4. 作为 DelayQueue / 定时任务的底层

常用方法复杂度一览

常见面试问题

相关文章

参考