Java Priority Queue

Intro

Java 中的 PriorityQueue 是一种特殊的队列数据结构，基于最小堆实现，支持优先级排序。它允许以自然顺序或自定义的比较器顺序对元素进行排序。这使得 PriorityQueue 特别适合处理需要频繁插入和删除操作的应用场景，如图算法、调度算法等。

本文将介绍 PriorityQueue 的使用方法，对原理进行简单探讨深入了我不会

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
….
Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe java.util.concurrent.PriorityBlockingQueue class.

一个基于优先级堆的无界优先队列。优先队列中的元素根据其自然顺序或在队列构造时提供的比较器进行排序，具体取决于使用的构造方法。优先队列不允许插入 null 元素。依赖自然顺序的优先队列同样不允许插入不可比较的对象（插入此类对象可能导致 ClassCastException 异常）。
…
请注意，该实现非线程安全的。如果多个线程中有任何一个线程修改队列，那么它们不应该同时访问同一个 PriorityQueue 实例。相反，应使用线程安全的 java.util.concurrent.PriorityBlockingQueue 类。
https://docs.oracle.com/en/java/javase/22/docs/api/java.base/java/util/PriorityQueue.html

使用方法

创建 PriorityQueue

在 Java 中，可以使用 PriorityQueue 类创建优先队列。其基本构造方法如下：

1

PriorityQueue<Type> queue = new PriorityQueue<>();

Methods

PriorityQueue 提供了多种方法来添加和删除元素：

• add(E e)：方法用于将元素添加到 PriorityQueue 中。如果队列容量不足，它会自动扩容。在添加元素后，优先队列会调整内部的堆结构，确保最小堆的性质得到保持
• offer(E e)：与 add 方法功能几乎相同，都是用于将元素插入优先队列中，但队列容量不足时不会抛出异常，而是返回 false 表示插入失败
• peek()：查看优先队列中优先级最高的元素（最小的元素），但不移除它。如果队列为空，返回 null。
• poll()：方法用于从优先队列中移除并返回优先级最高的元素（最小的元素）。它通过堆结构的调整来维护最小堆的性质。与 peek() 不同，poll() 会修改队列
• clear：从这个优先级队列中删除所有元素
• contains(Object o)：判断队列是否包含某个元素
• remove(Object o) ：从队列中移除指定元素，如果元素存在则返回 true，否则返回 false
• ……

Examples

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(5);
        queue.add(1);
        queue.add(3);

        System.out.println("queue.peek()：" + queue.peek()); // 1
        System.out.println("queue.poll()：" + queue.poll()); // 1
        System.out.println("queue.peek()：" + queue.peek()); // 3
    }
}

自定义优先级

可以通过实现 Comparator 接口来自定义优先级

在操作系统中的任务调度场景中，优先级队列（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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

import java.util.PriorityQueue;

// 定义任务类
class Task implements Comparable<Task> {
    private String name;      // 任务名称
    private int priority;     // 任务优先级，数字越小优先级越高

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    // 获取任务名称
    public String getName() {
        return name;
    }

    // 获取任务优先级
    public int getPriority() {
        return priority;
    }

    // 定义比较方法，根据优先级排序
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority); // 优先级越小越优先
    }

    // 打印任务信息
    @Override
    public String toString() {
        return "Task{name='" + name + "', priority=" + priority + "}";
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        // 创建优先级队列，用于调度任务
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();

        // 添加任务到队列
        taskQueue.add(new Task("System Update", 1));  // 高优先级任务
        taskQueue.add(new Task("Backup", 3));         // 低优先级任务
        taskQueue.add(new Task("Email Sync", 2));     // 中优先级任务
        taskQueue.add(new Task("User Report Generation", 4)); // 更低优先级任务

        // 调度任务：按优先级顺序执行
        System.out.println("Task scheduling started...\n");
        int count = 1;
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll(); // 取出并移除优先级最高的任务
            System.out.println("Executing: " + task.getName() + " with priority " + task.getPriority());
            
            // 模拟在执行第二个任务时突然插入优先级为0的插队任务
            if (count == 2) {
                Task emergencyTask = new Task("Emergency Task", 0); // 优先级为0的插队任务
                System.out.println("\n*** New task arrives: " + emergencyTask.getName() + " with priority " + emergencyTask.getPriority() + " ***\n");
                taskQueue.add(emergencyTask); // 插队任务进入队列
            }

            // 执行任务的逻辑
            simulateTaskExecution(task);
            count++;
        }

        System.out.println("\nAll tasks completed.");
    }

    // 模拟任务执行
    private static void simulateTaskExecution(Task task) {
        try {
            // 模拟任务执行的时间，这里假设每个任务需要 1 秒
            Thread.sleep(1000);
            System.out.println(task.getName() + " execution finished.\n");
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

执行结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Task scheduling started...

Executing: System Update with priority 1
System Update execution finished.

Executing: Email Sync with priority 2

*** New task arrives: Emergency Task with priority 0 ***

Email Sync execution finished.

Executing: Emergency Task with priority 0
Emergency Task execution finished.

Executing: Backup with priority 3
Backup execution finished.

Executing: User Report Generation with priority 4
User Report Generation execution finished.


All tasks completed.

更多应用场景

• 急诊室：在医院急诊室，患者根据病情的严重程度进行分类，病情危重的患者首先接受治疗。优先级队列可用于管理医生和护士查看患者的顺序。
• 网络路由：在计算机网络中，优先级队列用于管理数据包的流动。像语音和视频数据这样的高优先级数据包可以优先于像电子邮件和文件传输这样的低优先级数据。
• 在线市场：在在线市场中，优先级队列可用于管理向客户交付产品。高优先级的订单，可以优先于标准运输订单。

原理探讨

PriorityQueue 内部维护一个数组来存储元素，采用最小堆结构，通过数组下标来维护堆的性质：

• 根节点在数组索引 0 处。
• 对于每个索引 i：
  • 左子节点：2 * i + 1
  • 右子节点：2 * i + 2
  • 父节点：(i - 1) / 2

二叉堆（Binary Heap）是一种特殊的完全二叉树，它在实现优先队列等数据结构时被广泛应用。二叉堆具有以下两个主要特性：

• 结构特性（完全二叉树）：
  二叉堆是一棵完全二叉树，这意味着每一层都被完全填满，只有最后一层的节点可以不满，但必须从左向右依次排列。
• 堆特性（堆序性）：
  • 最大堆：每个节点的值都大于或等于其子节点的值，堆顶元素（根节点）是整个堆中最大的元素。
  • 最小堆：每个节点的值都小于或等于其子节点的值，堆顶元素（根节点）是整个堆中最小的元素。

1
2
3
4
5
6

最小堆示例
      2
     / \
    3   5
   / \   \
  6   8   10

二叉堆的应用

优先队列：

• 优先队列：通常使用最小堆实现。堆顶元素始终是最小值，可以快速查找、插入和删除最优元素。
• 堆排序：是一种基于二叉堆的排序算法，通过不断地将最大或最小元素放在堆的末尾，最终实现数组的排序。堆排序的时间复杂度为 O(n log n)，且不需要额外的存储空间。
• 图算法：Dijkstra算法、Prim算法等都需要频繁地从一组候选节点中选出最优节点并进行更新操作

Practice

• 23.合并K个排序链表
• …