PriorityQueue优先级队列用法

本文目录导读：

1. 基本概念
2. 创建优先级队列
3. 核心操作
4. 实际示例
5. 注意事项和性能
6. 实际应用场景

我来详细介绍 Java 中 PriorityQueue（优先级队列）的用法。

基本概念

PriorityQueue 是一种特殊的队列，元素按照优先级顺序出队，而不是 FIFO 顺序。

创建优先级队列

默认构造（最小堆）

// 自然顺序（最小堆）
PriorityQueue<Integer> pq = new PriorityQueue<>();

指定初始容量

PriorityQueue<Integer> pq = new PriorityQueue<>(20);

自定义比较器

// 最大堆（逆序）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

核心操作

基本方法

PriorityQueue<Integer> pq = new PriorityQueue<>();
// 添加元素
pq.offer(5);    // 推荐使用
pq.add(3);      // 也可以使用，但可能抛出异常
// 获取队首元素（不删除）
Integer peek = pq.peek();  // 返回 null 如果队列为空
// 获取并删除队首元素
Integer poll = pq.poll();  // 返回 null 如果队列为空
Integer remove = pq.remove(); // 抛出异常如果队列为空
// 其他方法
pq.size();      // 获取大小
pq.isEmpty();   // 是否为空
pq.clear();     // 清空队列

实际示例

示例1：Min Heap（最小堆）

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(5);
        minHeap.offer(1);
        minHeap.offer(3);
        System.out.println("队首元素: " + minHeap.peek());  // 1
        // 按顺序取出所有元素
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");  // 1 3 5
        }
    }
}

示例2：Max Heap（最大堆）

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = 
            new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(5);
        maxHeap.offer(1);
        maxHeap.offer(3);
        System.out.println("队首元素: " + maxHeap.peek());  // 5
        // 按顺序取出所有元素
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");  // 5 3 1
        }
    }
}

示例3：自定义对象

class Task implements Comparable<Task> {
    private String name;
    private int priority;
    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
    @Override
    public int compareTo(Task other) {
        // 优先级越高越先处理（数字越小优先级越高）
        return Integer.compare(this.priority, other.priority);
    }
    @Override
    public String toString() {
        return name + " (优先级: " + priority + ")";
    }
}
public class CustomObjectExample {
    public static void main(String[] args) {
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();
        taskQueue.offer(new Task("写代码", 1));
        taskQueue.offer(new Task("开会", 3));
        taskQueue.offer(new Task("吃饭", 5));
        taskQueue.offer(new Task("修Bug", 2));
        // 按优先级处理任务
        while (!taskQueue.isEmpty()) {
            System.out.println("处理: " + taskQueue.poll());
        }
    }
}

示例4：自定义比较器

class Student {
    String name;
    double score;
    Student(String name, double score) {
        this.name = name;
        this.score = score;
    }
}
public class ComparatorExample {
    public static void main(String[] args) {
        // 按成绩降序排列
        PriorityQueue<Student> pq = new PriorityQueue<>(
            (s1, s2) -> Double.compare(s2.score, s1.score)
        );
        pq.offer(new Student("张三", 85.5));
        pq.offer(new Student("李四", 92.0));
        pq.offer(new Student("王五", 78.0));
        while (!pq.isEmpty()) {
            Student s = pq.poll();
            System.out.println(s.name + ": " + s.score);
        }
    }
}

示例5：Top K 问题

public class TopKExample {
    public static int[] findTopK(int[] nums, int k) {
        if (k <= 0) return new int[0];
        // 使用最小堆维护前 k 个最大元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        // 转换为数组
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int[] top3 = findTopK(nums, 3);
        System.out.println("前3个最大数: " + Arrays.toString(top3));
    }
}

注意事项和性能

// 1. 不允许 null 元素
pq.offer(null);  // NullPointerException
// 2. 线程不安全
// 使用 ConcurrentLinkedQueue 或 PriorityBlockingQueue 替代
// 3. 时间复杂度
// offer, poll, remove, add - O(log n)
// peek, element, size - O(1)
// 4. 迭代器不保证顺序
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
// 下面的遍历不保证有序
for (Integer num : pq) {
    System.out.print(num + " ");  // 可能输出: 1 3 2
}
// 正确的方式是使用 poll
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");  // 1 2 3
}

实际应用场景

// 1. 任务调度
PriorityQueue<Task> taskQueue;  // 按优先级执行
// 2. 合并有序数组
PriorityQueue<ArrayEntry> heap;  // 多路归并
// 3. 求中位数
// 使用两个堆：最大堆+最小堆
// 4. 数据流中的第k大元素
// 维护大小为k的最小堆

PriorityQueue 的主要特点：

• 默认最小堆（优先级高的先出队）
• 可自定义比较器实现不同排序
• O(log n) 入队出队，O(1) 获取队首
• 线程不安全，需要线程安全使用 PriorityBlockingQueue
• 不允许 null 元素

选择合适的比较器可以轻松实现最大堆、最小堆以及基于对象属性的优先级排序。