小菜鸟

java菜鸟号正在起航

0%

PriorityQueue详解

发表于 更新于 分类于 阅读次数： 143 Valine： 0
本文字数： 6.4k 阅读时长 ≈ 6 分钟

PriorityQueue 详解：Java 中的优先级队列

PriorityQueue 是 Java 集合框架中基于二叉堆实现的优先级队列，它能够保证每次取出的元素都是队列中优先级最高的（默认是自然排序的最小值）。与普通队列的 “先进先出” 不同，PriorityQueue 的元素顺序由优先级决定，适用于需要动态获取最值的场景（如任务调度、Top K 问题等）。

核心特性

  1. 底层结构：基于二叉堆（完全二叉树），使用数组存储，空间效率高。
  2. 排序方式：支持自然排序（元素实现 Comparable）或定制排序（传入 Comparator）。
  3. 无界队列：容量可动态扩容（默认初始容量 11），理论上没有上限（受限于内存）。
  4. 时间复杂度：插入（offer）和删除（poll）操作的时间复杂度为 O(log n)，获取最值（peek）为 O(1)。
  5. 非线程安全：多线程环境需使用 PriorityBlockingQueue（并发版本）。
  6. 不允许 null 元素：插入 null 会抛出 NullPointerException。

底层数据结构：二叉堆

PriorityQueue 的核心是二叉堆，它是一种满足以下性质的完全二叉树：

  1. 结构性：是一棵完全二叉树（除最后一层外，每一层都被填满；最后一层的节点靠左排列）。

  2. 堆序性：

    • 小顶堆（默认）：每个节点的值 ≤ 其左右子节点的值（根节点是最小值）。
 <pre class="mermaid">     graph TD
 0((0)) --- 1((1)) --- 3((3))
 1((1)) --- 4((4))
 0((0)) --- 2((2))</pre>
  • 大顶堆：每个节点的值 ≥ 其左右子节点的值（根节点是最大值）。
 <pre class="mermaid">     graph TD
 0((4)) --- 1((3)) --- 3((1))
 1((3)) --- 4((0))
 0((4)) --- 2((2))</pre>

堆的数组表示

完全二叉树的特性使得堆可以用数组高效存储，父子节点的索引关系如下：

  • 对于索引为i的节点：
    • 左子节点索引：2*i + 1
    • 右子节点索引：2*i + 2
    • 父节点索引：(i - 1) >>> 1（等价于 (i-1)/2，无符号右移避免负数问题）

例如，小顶堆的数组表示：

1
2
3
4
5
6
7
数组：[1, 3, 2, 6, 5, 4]
对应堆结构：
      1
    /   \
   3     2
  / \   /
 6  5  4

小顶堆与大顶堆

  • 小顶堆：根节点是最小值，每次 poll 操作取出最小值。
  • 大顶堆：根节点是最大值，需通过定制比较器实现（Comparator.reverseOrder()）。

核心源码解析（JDK 8）

重要属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;

// 存储堆元素的数组（完全二叉树的数组表示）
transient Object[] queue;

// 元素数量
private int size = 0;

// 比较器（null 表示自然排序，默认小顶堆）
private final Comparator<? super E> comparator;

// 修改次数（用于迭代器的 fail-fast 机制）
transient int modCount = 0;

// 最大容量（避免 Integer 溢出）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

PriorityQueue 提供多种构造函数，核心是初始化容量和比较器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 1. 默认构造器（初始容量 11，自然排序）
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

// 2. 指定初始容量（自然排序）
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

// 3. 指定比较器（初始容量 11）
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

// 4. 核心构造器（指定容量和比较器）
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

// 5. 从集合初始化（根据集合类型决定比较器）
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        // 从 SortedSet 初始化，复用其比较器
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    } else if (c instanceof PriorityQueue<?>) {
        // 从 PriorityQueue 初始化，复用其比较器
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    } else {
        // 其他集合，使用自然排序
        this.comparator = null;
        initFromCollection(c);
    }
}

核心操作：插入（offer）

插入元素时，需维持堆的性质（小顶堆或大顶堆），步骤如下：

  1. 扩容（若数组已满）；
  2. 将元素插入数组末尾；
  3. 向上调整（siftUp）：将新元素与父节点比较，若不符合堆序则交换，直到满足堆序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException(); // 不允许 null
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1); // 扩容
    size = i + 1;
    if (i == 0)
        queue[0] = e; // 第一个元素直接作为根节点
    else
        siftUp(i, e); // 向上调整
    return true;
}

// 扩容逻辑
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 容量 <64 时，扩容为 old + (old + 2)；否则扩容 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // 处理溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

// 向上调整（自然排序，小顶堆）
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;
}

示例：向小顶堆 [1,3,2] 插入元素 0

  • 插入末尾：[1,3,2,0]
  • 向上调整：
    • 0（索引 3）的父节点是 3（索引 1），0 < 3 → 交换 → [1,0,2,3]
    • 0（索引 1）的父节点是 1（索引 0），0 < 1 → 交换 → [0,1,2,3]
  • 结果：[0,1,2,3]（满足小顶堆）

核心操作：删除（poll）

删除堆顶元素（优先级最高的元素），步骤如下：

  1. 取出堆顶元素；
  2. 将数组末尾元素移到堆顶；
  3. 向下调整（siftDown）：将堆顶元素与子节点比较，若不符合堆序则交换，直到满足堆序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0]; // 堆顶元素（结果）
    E x = (E) queue[s]; // 末尾元素
    queue[s] = null; // 清空末尾
    if (s != 0)
        siftDown(0, x); // 向下调整
    return result;
}

// 向下调整（自然排序，小顶堆）
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    int half = size >>> 1; // 非叶子节点的最大索引
    while (k < half) {
        int child = (k << 1) + 1; // 左子节点索引
        Object c = queue[child];
        int right = child + 1; // 右子节点索引
        // 选择左右子节点中较小的一个
        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;
}

示例：从小顶堆 [0,1,2,3] 中 poll 元素

  • 取出堆顶 0，末尾元素 3 移到堆顶 → [3,1,2,null]
  • 向下调整：
    • 3（索引 0）的左右子节点为 1（索引 1）和 2（索引 2），选择较小的 1 → 3 > 1 交换 → [1,3,2,null]
    • 3（索引 1）的左右子节点为 3（索引 3，已空），停止调整。
  • 结果：[1,3,2]（满足小顶堆），返回 0

其他常用方法

  • peek()：获取堆顶元素（不删除），直接返回 queue[0]。
  • remove(Object o)：删除指定元素，需先遍历数组找到索引，再通过 removeAt 方法删除并调整堆。
  • size()：返回元素数量 size。

使用示例

1. 自然排序（小顶堆）

1
2
3
4
5
6
7
8
9
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);

System.out.println(pq.peek()); // 1（堆顶是最小值）
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " "); // 1 2 3（按优先级出队）
}

2. 定制排序（大顶堆）

1
2
3
4
5
6
7
8
9
10
// 使用 Comparator 实现大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);

System.out.println(maxHeap.peek()); // 3（堆顶是最大值）
while (!maxHeap.isEmpty()) {
    System.out.print(maxHeap.poll() + " "); // 3 2 1
}

3. 自定义对象排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Student implements Comparable<Student> {
    String name;
    int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    // 按分数升序排序（自然排序）
    @Override
    public int compareTo(Student o) {
        return Integer.compare(this.score, o.score);
    }
}

// 使用示例
PriorityQueue<Student> students = new PriorityQueue<>();
students.offer(new Student("Alice", 90));
students.offer(new Student("Bob", 80));
students.offer(new Student("Charlie", 95));

// 按分数从小到大出队
while (!students.isEmpty()) {
    System.out.println(students.poll().name); // Bob（80）→ Alice（90）→ Charlie（95）
}

注意事项

  1. 迭代顺序不保证有序：PriorityQueue 的迭代器（iterator()）不按优先级顺序遍历，若需有序遍历，需多次调用 poll() 方法。
  2. 扩容策略：初始容量 11，当容量 <64 时每次扩容增加 old + 2，否则增加 50%，避免频繁扩容。
  3. 与 TreeSet 的区别：
    • PriorityQueue 是队列，允许重复元素；TreeSet 是集合，不允许重复，且全量有序。
    • PriorityQueue 侧重动态获取最值；TreeSet 侧重范围查询和全量排序
相关文章

欢迎关注我的其它发布渠道

表情 | 预览
快来做第一个评论的人吧~
Powered By Valine
v1.3.10