一、什么是优先级队列？

1. 核心定义

优先级队列是一种有序队列，区别于普通队列 “先进先出（FIFO）” 的规则，它的出队顺序由元素的优先级决定：

• 每次调用poll()（出队）或peek()（查看队首）时，返回的是队列中优先级最高（或最低）的元素；

• 元素的优先级可通过自然排序（实现Comparable接口）或自定义比较器（Comparator）指定；

• Java 中PriorityQueue是无界队列（默认初始容量 11，可自动扩容），线程不安全；并发场景下需用PriorityBlockingQueue（阻塞优先级队列）。

2. 与普通队列的区别

特性	普通队列（LinkedList/ArrayDeque）	优先级队列（PriorityQueue）
排序规则	先进先出（FIFO）/ 后进先出（LIFO）	按元素优先级排序（自然序 / 自定义）
出队元素	队首元素（最早入队）	优先级最高 / 最低元素
底层实现	链表 / 数组	二叉堆（默认小顶堆）
线程安全	不安全（需手动同步）	不安全（并发用 PriorityBlockingQueue）
容量特性	可无界 / 有界	默认无界（可指定初始容量）

3. 核心应用场景

• 任务调度：按任务优先级执行（如线程池中的延迟任务、优先级任务）；

• topK 问题：快速获取前 K 个最大 / 最小元素（如 Top10 热门商品、前 5 高分评论）；

• 最短路径算法：Dijkstra 算法中，用优先级队列选择当前最短路径节点；

• 事件驱动：按事件紧急程度处理（如系统告警、消息推送）。

二、优先级队列的底层原理：二叉堆

Java 的PriorityQueue底层基于二叉堆（Binary Heap） 实现，这是一种完全二叉树结构，分为 “小顶堆” 和 “大顶堆”：

• 小顶堆：每个父节点的值 ≤ 其子节点的值，队首（堆顶）是最小值（Java 默认）；

• 大顶堆：每个父节点的值 ≥ 其子节点的值，队首（堆顶）是最大值。

1. 完全二叉树与数组存储

二叉堆是完全二叉树（除最后一层外，每一层节点数都满，最后一层从左到右连续），因此可以用数组高效存储：

• 若父节点索引为i，则左子节点索引 = 2*i + 1，右子节点索引 = 2*i + 2；

• 若子节点索引为j，则父节点索引 = (j - 1) / 2（整数除法）。

例：小顶堆的数组存储结构（元素：[1,3,2,5,4]）：

数组索引：0 1 2 3 4
元素值：   1 3 2 5 4
对应的完全二叉树：
        1（0）
      /   \
     3（1）2（2）
    / \
   5（3）4（4）

2. 堆的核心操作（维护堆特性）

优先级队列的入队（offer()）和出队（poll()）操作，本质是堆的 “上浮（siftUp）” 和 “下沉（siftDown）”，目的是维护堆的有序性。

（1）入队：siftUp（上浮）

当新元素入队时，插入到数组末尾（完全二叉树的最后一个节点），然后通过 “上浮” 调整位置，直到满足堆特性：

1. 新元素索引j = 数组长度 - 1；
2. 计算父节点索引i = (j-1)/2；
3. 比较新元素与父节点：若新元素优先级更高（小顶堆中值更小），则交换两者；
4. 重复步骤 2-3，直到父节点优先级更高或到达堆顶（j=0）。

例：向上述小顶堆中插入元素0：

• 插入后数组：[1,3,2,5,4,0] → 新元素索引5，父节点索引2（元素2）；

• 0 → 数组：[1,3,0,5,4,2] → 新元素索引2，父节点索引0（元素1）；

• 0 交换 → 数组：[0,3,2,5,4,1] → 到达堆顶，上浮结束。

（2）出队：siftDown（下沉）

当堆顶元素出队时，用数组末尾元素替换堆顶，然后通过 “下沉” 调整位置，直到满足堆特性：

1. 堆顶元素（索引0）出队，将末尾元素（索引size-1）移到堆顶，数组长度减 1；
2. 当前节点索引i=0，计算左右子节点索引left=1、right=2；
3. 找到左右子节点中优先级最高的节点（小顶堆中值最小），记为minChildIndex；
4. 比较当前节点与minChildIndex对应的元素：若当前节点优先级更低，则交换两者；
5. 重复步骤 2-4，直到当前节点优先级更高或无子节点（left >= size）。

例：从上述小顶堆 [0,3,2,5,4,1] 中出队（取出0）：

• 末尾元素1移到堆顶 → 数组：[1,3,2,5,4]（size=5）；

• 当前节点1（索引0），左右子节点3（索引1）、2（索引2） → 最小子节点是2（索引2）；

• 1 < 2 → 无需交换，下沉结束（堆仍满足小顶堆特性）。

三、Java PriorityQueue 核心 API 与使用

1. 构造方法（4 种常用）

PriorityQueue提供多个构造方法，核心是指定 “初始容量” 和 “排序规则”：

// 1. 默认构造：初始容量11，自然排序（元素需实现Comparable）
PriorityQueue<Integer> pq1 = new PriorityQueue// 2. 指定初始容量：容量可自动扩容，自然排序
PriorityQueue<Integer> pq2 = new PriorityQueue);

// 3. 自定义比较器：指定优先级规则（如大顶堆）
PriorityQueue> maxHeap = new PriorityQueue) -> b - a);

// 4. 从集合初始化：将集合元素转为优先级队列
List<Integer> list = Arrays.asList(3,1,2);
PriorityQueue pq4 = new PriorityQueue

⚠️ 注意：
- 若使用自然排序，元素必须实现`Comparable`接口（如`Integer`、`String`），否则会抛出`ClassCastException`；
- 初始容量只是“初始大小”，队列满时会自动扩容（扩容规则：当容量<64时翻倍，≥64时扩容50%）。

### 2. 核心方法（常用操作）
| 方法名         | 功能描述                                  | 注意点                                  |
|----------------|-------------------------------------------|-----------------------------------------|
| `offer(E e)`   | 入队：添加元素，返回true（无界队列，永不失败） | 触发siftUp操作                          |
| `poll()`       | 出队：取出并删除堆顶元素，队列为空返回null | 触发siftDown操作                        |
| `peek()`       | 查看堆顶元素，队列为空返回null            | 不修改队列，仅查询                      |
| `size()`       | 返回队列中元素个数                        | -                                       |
| `isEmpty()`    | 判断队列是否为空                          | -                                       |
| `clear()`      | 清空队列                                  | -                                       |
| `contains(Object o)` | 判断是否包含指定元素                  | 遍历整个数组，时间复杂度O(n)            |
| `toArray()`    | 转为数组返回                              | 数组元素无序（仅存储结构，未排序）       |

### 3. 关键使用示例
#### （1）自然排序（小顶堆）
```java
public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue new PriorityQueue        // 入队
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);
        
        // 出队（按优先级：1→2→5→8）
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // 输出：1 2 5 8
        }
    }
}

（2）自定义比较器（大顶堆）

通过Comparator接口指定 “大的元素优先级高”：

public class MaxHeapDemo {
    public static void main(String[] args) {
        // 自定义比较器：b - a 表示“a 优先级更高”
        PriorityQueue new PriorityQueue, b) -> b - a);
        
        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);
        
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " "); // 输出：8 5 2 1
        }
    }
}

（3）存储自定义对象（需实现 Comparable）

自定义User类，按age升序排序（自然排序）：

class User implements Comparable> {
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // 自然排序：按age升序（age越小，优先级越高）
    @Override
    public int compareTo(User o) {
        return this.age - o.age;
    }

    @Override
    public String toString() {
        return "User{name='" + name + "', age=" + age + "}";
    }
}

public class CustomObjectDemo {
    public static void main(String[] args) {
        PriorityQueueq = new PriorityQueue();
        pq.offer(new User("张三", 25));
        pq.offer(new User("李四", 20));
        pq.offer(new User("王五", 30));
        
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); 
            // 输出：
            // User{name='李四', age=20}
            // User{name='张三', age=25}
            // User{name='王五', age=30}
        }
    }
}

四、PriorityQueue 源码核心逻辑解析（JDK8）

1. 核心成员变量

public class PriorityQueue<E> extends AbstractQueue> {
    private transient Object[] queue; // 存储堆的数组
    private int size; // 元素个数
    private final Comparator comparator; // 比较器（null表示自然排序）
    private static final int DEFAULT_INITIAL_CAPACITY = 11; // 默认初始容量
}

2. 入队（offer ()）源码

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时翻倍，≥64时扩容50%
    int newCapacity = oldCapacity + ((oldCapacity ) ? (oldCapacity + 2) : (oldCapacity >> 1));
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

// 上浮操作（根据是否有比较器选择不同实现）
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x); // 自定义比较器
    else
        siftUpComparable(k, x); // 自然排序
}

// 自然排序的上浮
private void siftUpComparable(int k, E x) {
    Comparable super E> key = (Comparable x;
    while (k > 0) {
        int parent = (k - 1) >>> 1; // 父节点索引（等价于(k-1)/2，无符号右移）
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break; // 父节点优先级更高，停止上浮
        queue[k] = e; // 父节点下沉
        k = parent; // 继续向上比较
    }
    queue[k] = key;
}

3. 出队（poll ()）源码

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 siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

// 自然排序的下沉
private void siftDownComparable(int k, E x) {
    Comparable> key = (Comparable<? super E>) x;
    int half = size >>> 1; // 非叶子节点的最大索引（叶子节点无需下沉）
    while (k < half) {
        int left = (k <1) + 1; // 左子节点索引
        int right = left + 1; // 右子节点索引
        Object c = queue[left]; // 左子节点
        // 选择左右子节点中优先级更高的（小顶堆选更小的）
        if (right able).compareTo((E) queue[right]) > 0)
            c = queue[right];
        if (key.compareTo((E) c) 0)
            break; // 当前节点优先级更高，停止下沉
        queue[k] = c; // 子节点上浮
        k = left; // 继续向下比较
    }
    queue[k] = key;
}

4. 关键源码总结

• 不允许存储null元素（offer()直接抛空指针）；

• 扩容规则：容量 < 64 时翻倍 + 2，≥64 时扩容 50%；

• 排序依赖Comparable（自然排序）或Comparator（自定义排序）；

• 核心操作offer()和poll()的时间复杂度为O(log n)（堆的高度是log2(n)）。

五、并发安全的优先级队列：PriorityBlockingQueue

PriorityQueue是线程不安全的，多线程环境下需使用java.util.concurrent.PriorityBlockingQueue（阻塞优先级队列），它的核心特性：

1. 基于PriorityQueue实现，保留优先级排序特性；
2. 线程安全：通过ReentrantLock保证入队 / 出队操作的原子性；
3. 阻塞特性：

• • 队列为空时，take()会阻塞直到有元素；

• • 队列满时（有界），put()会阻塞直到有空闲位置（默认无界，可指定容量）；

    4.无界特性：默认初始容量 11，满时自动扩容（与PriorityQueue一致）。

核心使用示例

import java.util.concurrent.PriorityBlockingQueue;

public class PriorityBlockingQueueDemo {
    public static void main(String[] args) throws InterruptedException {
        // 大顶堆（自定义比较器）
        PriorityBlockingQueue = new PriorityBlockingQueue((a, b) -> b - a);
        
        // 生产者线程：入队
        new Thread(() -> {
            try {
                pbq.put(3);
                pbq.put(1);
                pbq.put(2);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }).start();
        
        // 消费者线程：出队
        new Thread(() -> {
            try {
                System.out.println(pbq.take()); // 输出：3
                System.out.println(pbq.take()); // 输出：2
                System.out.println(pbq.take()); // 输出：1
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }).start();
    }
}

六、手写优先级队列（模拟实现）

基于二叉堆的原理，手写一个简易版优先级队列（支持自然排序和自定义比较器）：

import java.util.Arrays;
import java.util.Comparator;

public class MyPriorityQueue
    private Object[] queue; // 存储堆的数组
    private int size; // 元素个数
    private Comparator E> comparator; // 比较器
    private static final int DEFAULT_CAPACITY = 11; // 默认初始容量

    // 构造方法1：默认容量+自然排序
    public MyPriorityQueue() {
        this(DEFAULT_CAPACITY, null);
    }

    // 构造方法2：指定容量+自然排序
    public MyPriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    // 构造方法3：指定容量+自定义比较器
    public MyPriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity             throw new IllegalArgumentException("初始容量不能小于1");
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    // 入队
    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException("元素不能为null");
        // 扩容判断
        if (size >= queue.length)
            grow();
        // 插入元素并上浮
        if (size == 0)
            queue[0] = e;
        else
            siftUp(size, e);
        size++;
        return true;
    }

    // 出队
    public E poll() {
        if (size == 0)
            return null;
        size--;
        E top = (E) queue[0]; // 堆顶元素
        E last = (E) queue[size]; // 末尾元素
        queue[size] = null; // 清空末尾
        // 下沉调整
        if (size > 0)
            siftDown(0, last);
        return top;
    }

    // 查看堆顶
    public E peek() {
        return size == 0 ? null : (E) queue[0];
    }

    // 扩容
    private void grow() {
        int oldCapacity = queue.length;
        // 扩容规则：4时翻倍+2，≥64时扩容50%
        int newCapacity = oldCapacity + (oldCapacity  ? (oldCapacity + 2) : (oldCapacity >> 1));
        queue = Arrays.copyOf(queue, newCapacity);
    }

    // 上浮操作
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpWithComparator(k, x);
        else
            siftUpWithComparable(k, x);
    }

    // 自然排序的上浮
    private void siftUpWithComparable(int k, E x) {
        Comparable super E> key = (Comparable x;
        while (k > 0) {
            int parent = (k - 1) >>> 1; // 父节点索引
            E parentVal = (E) queue[parent];
            if (key.compareTo(parentVal) >= 0)
                break; // 父节点优先级更高，停止
            // 父节点下沉
            queue[k] = parentVal;
            k = parent;
        }
        queue[k] = key;
    }

    // 自定义比较器的上浮
    private void siftUpWithComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            E parentVal = (E) queue[parent];
            if (comparator.compare(x, parentVal) >= 0)
                break;
            queue[k] = parentVal;
            k = parent;
        }
        queue[k] = x;
    }

    // 下沉操作
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownWithComparator(k, x);
        else
            siftDownWithComparable(k, x);
    }

    // 自然排序的下沉
    private void siftDownWithComparable(int k, E x) {
        Comparable<? super E> key = (Comparable>) x;
        int half = size >>> 1; // 非叶子节点的最大索引
        while (k 
            int left = (k < 1; // 左子节点
            int right = left + 1; // 右子节点
            E minChild = (E) queue[left];

            // 选择左右子节点中优先级更高的
            if (right < size && ((Comparable super E>) minChild).compareTo((E) queue[right]) > 0)
                minChild = (E) queue[right];

            if (key.compareTo(minChild)  0)
                break; // 当前节点优先级更高，停止

            queue[k] = minChild;
            k = left;
        }
        queue[k] = key;
    }

    // 自定义比较器的下沉
    private void siftDownWithComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            int left = (k <1) + 1;
            int right = left + 1;
            E minChild = (E) queue[left];

            if (right  && comparator.compare(minChild, (E) queue[right]) > 0)
                minChild = (E) queue[right];

            if (comparator.compare(x, minChild)  0)
                break;

            queue[k] = minChild;
            k = left;
        }
        queue[k] = x;
    }

    // 辅助方法：获取元素个数
    public int size() {
        return size;
    }

    // 测试
    public static void main(String[] args) {
        // 测试大顶堆
        MyPriorityQueue<Integer> maxHeap = new MyPriorityQueue, b) -> b - a);
        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);

        System.out.println("大顶堆出队顺序：");
        while (maxHeap.size() > 0) {
            System.out.print(maxHeap.poll() + " "); // 输出：8 5 2 1
        }

        // 测试小顶堆（自然排序）
        MyPriorityQueue = new MyPriorityQueue();
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);

        System.out.println("\n小顶堆出队顺序：");
        while (minHeap.size() > 0) {
            System.out.print(minHeap.poll() + " "); // 输出：1 2 5 8
        }
    }
}

七、优先级队列的常见问题与注意事项

1. 线程安全问题

• PriorityQueue线程不安全，多线程同时入队 / 出队会导致数据错乱；

• 并发场景必须用PriorityBlockingQueue（阻塞）或手动加锁（synchronized/Lock）。

2. 无界队列的 OOM 风险

• PriorityQueue和PriorityBlockingQueue默认无界，若入队速度远大于出队速度，会导致元素堆积，最终 OOM；

• 解决方案：使用PriorityBlockingQueue时指定容量（有界），配合拒绝策略（需自定义）。

3. 元素排序的一致性

• 若元素是自定义对象，需保证Comparable的compareTo()方法或Comparator的compare()方法逻辑一致，否则会导致排序异常；

• 例：compareTo()返回this.age - o.age表示升序，若中途修改为o.age - this.age，会破坏堆结构。

4. 遍历无序问题

• PriorityQueue的iterator()遍历结果是无序的（仅按数组存储顺序），若需有序遍历，需通过poll()逐个取出（会删除元素）或复制到数组后排序。

八、总结（面试必背）

1. 优先级队列：按元素优先级排序，出队取优先级最高元素，底层是二叉堆（小顶堆默认）；
2. 核心操作：入队（siftUp）、出队（siftDown），时间复杂度O(log n)；
3. Java 实现：

• • PriorityQueue：无界、线程不安全，支持自然排序 / 自定义比较器；

• • PriorityBlockingQueue：无界 / 有界、线程安全、阻塞，适用于并发场景；
• 关键考点：
• • 二叉堆的存储结构与核心操作；

• • 自定义比较器实现大顶堆；

• • 线程安全的替代方案；

• • 手写优先级队列（堆的上浮 / 下沉）；

实战场景：TopK 问题、任务调度、最短路径算法等。