【Java集合夜话】第8篇上：PriorityQueue优先队列详解，从源码到实战，一文吃透堆数据结构（建议收藏）

🔥 本文深入剖析Java中的优先队列PriorityQueue，从堆的基本概念到源码实现原理，带你全面理解这个重要的数据结构。由于内容较多，分为上下两篇，本篇是上篇，主要讲解基础概念和源码分析。

📚 系列专栏推荐：

• JAVA集合【夜话集】
• JVM知识专栏
• 数据库sql理论与实战【博主踩坑之道】
• 小游戏开发【博主强推 匠心之作 拿来即用无门槛】

1. 优先队列基础

1.1 什么是优先队列？

想象你正在医院的急诊室。虽然病人按到达顺序排队，但突然来了一位急重症病人，医生会优先处理这位病人。这就是现实生活中的"优先队列"：不是先来先服务，而是按照优先级处理。

1.1.1 与普通队列的区别

普通队列就像我们排队买奶茶：

• 先来的人先买
• 后来的人后买
• 严格遵循"先进先出"(FIFO)原则

而优先队列则像医院的急诊室：

• 不是先来先服务
• 而是按照事件的紧急程度
• 优先级高的先处理
• 优先级相同时，先来先服务

让我们用代码来直观感受一下区别：

// 普通队列
Queue<String> normalQueue = new LinkedList<>();
normalQueue.offer("小明");
normalQueue.offer("小红");
normalQueue.offer("小张");
// 处理顺序：小明 -> 小红 -> 小张// 优先队列
PriorityQueue<Patient> emergencyRoom = new PriorityQueue<>((p1, p2) -> p2.getEmergencyLevel() - p1.getEmergencyLevel());
emergencyRoom.offer(new Patient("小明", 1)); // 普通感冒
emergencyRoom.offer(new Patient("小红", 3)); // 高烧
emergencyRoom.offer(new Patient("小张", 2)); // 扭伤
// 处理顺序：小红(高烧) -> 小张(扭伤) -> 小明(感冒)

1.1.2 优先级的概念

优先级可以基于多种规则：

1. 自然顺序

• 数字：越小越优先
• 字符串：字典序越小越优先

// 数字优先队列（小顶堆）
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(3);
numbers.offer(1);
numbers.offer(2);
System.out.println(numbers.poll()); // 输出1

2. 自定义顺序

• 根据业务需求定义优先级
• 通过Comparator实现自定义排序

// 工作任务队列（按优先级排序）
PriorityQueue<Task> taskQueue = new PriorityQueue<>((t1, t2) -> {// 先比较优先级if (t1.getPriority() != t2.getPriority()) {return t2.getPriority() - t1.getPriority();}// 优先级相同，比较创建时间return t1.getCreateTime().compareTo(t2.getCreateTime());
});

1.1.3 实际应用场景

优先队列在我们的日常生活和系统开发中随处可见：

1. 操作系统的进程调度

• 高优先级进程优先获得CPU时间片
• 系统进程优先级高于用户进程
• 前台进程优先级高于后台进程

2. 打印机任务队列

• 紧急文件优先打印
• 老板的文件优先级更高
• 大文件可能优先级较低

3. 游戏排位匹配系统

class Player {private String name;private int ranking;private long waitTime;// ... 其他属性
}PriorityQueue<Player> matchQueue = new PriorityQueue<>((p1, p2) -> {// 等待时间越长，优先级越高long timeDiff = p2.getWaitTime() - p1.getWaitTime();if (timeDiff != 0) {return (int)timeDiff;}// 等待时间相同，按照排位分数匹配return Math.abs(p1.getRanking() - targetRanking) - Math.abs(p2.getRanking() - targetRanking);
});

4. 网络请求处理

• VIP用户请求优先处理
• 支付请求优先于查询请求
• 实时性要求高的请求优先

通过这些例子，我们可以看到优先队列的核心特点：

• 动态调整处理顺序
• 基于优先级的灵活排序
• 在插入时自动维护顺序
• 保证每次取出的都是当前最优先的元素

理解了优先队列的本质，我们就能更好地在实际开发中运用它，设计出更合理的系统。接下来，我们将深入探讨它的底层实现原理——堆数据结构。

1.2 底层数据结构：堆

要理解优先队列，我们必须先理解它的底层数据结构——堆。想象一个公司的组织架构：CEO在最顶端，下面是经理，再下面是普通员工。堆的结构也是类似的层级关系。

1.2.1 什么是堆？

堆是一种特殊的完全二叉树，它满足以下特性：

• 结构性：是一个完全二叉树
• 有序性：任意节点的值总是大于（或小于）其子节点的值

就像公司架构：

• 完全二叉树：每层都尽可能填满，新人从左到右依次加入
• 有序性：职级高的总是在上层（类比大顶堆）

1.2.2 最大堆vs最小堆

1. 最大堆（大顶堆）

• 父节点的值总是大于或等于子节点
• 堆顶是最大元素

// 最大堆示例
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(1);
maxHeap.offer(5);
maxHeap.offer(3);
System.out.println(maxHeap.peek()); // 输出5

2. 最小堆（小顶堆）

• 父节点的值总是小于或等于子节点
• 堆顶是最小元素

// 最小堆示例（PriorityQueue默认实现）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.peek()); // 输出1

1.2.3 完全二叉树的性质

想象一个电影院的座位安排：

• 从前往后，从左到右依次坐满
• 最后一排可能不满，但一定是从左往右坐的

完全二叉树的特点：

1. 结构特性

   • 除最后一层外，其他层都是满的
   • 最后一层的节点从左到右填充
   • 非常适合用数组存储

2. 节点关系（假设数组下标从0开始）

// 对于任意节点i
父节点索引 = (i - 1) / 2
左子节点索引 = 2 * i + 1
右子节点索引 = 2 * i + 2

3. 数组存储示意

// 数组：[10, 8, 9, 6, 7, 5, 4]
//      对应的完全二叉树结构
//         10
//        /  \
//       8    9
//      / \  / \
//     6   7 5  4

1.2.4 堆的基本操作

1. 插入元素（上浮）

• 新元素先放到末尾
• 与父节点比较，如果违反堆的性质则交换
• 重复直到满足堆的性质

// 上浮操作的核心逻辑
private void siftUp(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1; // 父节点索引if (x.compareTo(queue[parent]) >= 0)break;queue[k] = queue[parent];k = parent;}queue[k] = x;
}

2. 删除堆顶（下沉）

• 用最后一个元素替换堆顶
• 与子节点中较大（小）的比较，如果违反堆的性质则交换
• 重复直到满足堆的性质

就像公司裁员后的调整：

• CEO离职后，暂时由最基层员工代替
• 通过一系列晋升调整，直到位置合适

通过这些基本概念和操作，我们就能理解优先队列是如何高效地维护元素顺序的。接下来，我们将深入探讨这些操作的具体实现细节。

1.2.5 堆排序：一个有趣的应用

说到堆，就不得不提一个经典应用——堆排序。想象你在整理一叠扑克牌：

1. 建堆过程：

• 把散乱的牌先构造成一个堆
• 就像把员工按职级重新组织

2. 排序过程：

• 不断取出堆顶元素（最大或最小的）
• 就像公司按工资从高到低发工资

// 堆排序的简单示例
public static void heapSort(int[] arr) {// 建立大顶堆PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);for (int num : arr) {heap.offer(num);}// 依次取出堆顶元素for (int i = 0; i < arr.length; i++) {arr[i] = heap.poll();}
}

虽然堆排序不是最快的排序算法，但它有个很酷的特点：

• 不需要额外空间（原地排序）
• 最坏情况下也能保证O(nlogn)的时间复杂度
• 特别适合处理大数据流中的TopK问题

有趣的是，堆排序是唯一一个同时具备"原地排序"和"O(nlogn)"这两个特性的排序算法。

不过关于堆排序的具体细节，我们点到为止。因为我们今天的主角是优先队列，它才是堆这种数据结构最实用的应用。

理解了优先队列的本质，我们就能更好地在实际开发中运用它，设计出更合理的系统。接下来，我们将深入探讨它的底层实现原理——堆数据结构。

2. 核心原理

2.1 数组实现堆的精妙之处

在计算机世界中，有很多精妙的设计，而用数组实现堆绝对是其中最优雅的设计之一。想象一下，我们用一个一维数组，就能完美地表示一个树形结构，这是多么神奇的事情。

2.1.1 父子节点的完美映射

想象一个家族树，每个人都有一个编号，通过简单的数学计算就能找到父母和子女：

// 对于数组中的任意位置 i
int parent = (i - 1) / 2;     // 父节点的位置
int leftChild = 2 * i + 1;    // 左孩子的位置
int rightChild = 2 * i + 2;   // 右孩子的位置

这种对应关系的美妙之处在于：

• 无需存储额外的指针
• 通过简单的乘除法就能访问相关节点
• 完美利用了数组的连续存储特性

例如，对于数组 [10, 8, 9, 6, 7, 5, 4]：

         10(0)/     \8(1)     9(2)/   \    /   \6(3)  7(4) 5(5) 4(6)括号中的数字是数组索引

2.1.2 上浮(siftUp)操作的实现

当我们往堆中插入新元素时，需要进行上浮操作。就像公司新来了一个能力特别强的员工，需要一步步晋升到合适的职位：

private void siftUp(int k, E x) {while (k > 0) {// 找到父节点的位置int parent = (k - 1) >>> 1;// 如果父节点小于等于插入的值，就不用上浮了if (comparator.compare(x, queue[parent]) >= 0)break;// 否则，把父节点下移queue[k] = queue[parent];// 继续往上比较k = parent;}// 找到最终位置，放入元素queue[k] = x;
}

这个过程就像：

• 新人入职先坐到最后一个位置
• 跟上级比较能力
• 能力强就升职，上级下移
• 直到找到合适的位置

2.1.3 下沉(siftDown)操作的实现

当堆顶元素被删除后，我们需要将最后一个元素放到堆顶，然后执行下沉操作。这就像公司CEO离职，临时由普通员工代理，然后通过一系列调整找到合适的位置：

private void siftDown(int k, E x) {int half = size >>> 1;while (k < half) {// 找到左右子节点中较小的那个int child = (k << 1) + 1; // 左子节点int right = child + 1;    // 右子节点if (right < size && comparator.compare(queue[child], queue[right]) > 0)child = right;// 如果当前节点小于等于子节点，就不用下沉了if (comparator.compare(x, queue[child]) <= 0)break;// 否则，把较小的子节点上移queue[k] = queue[child];k = child;}// 找到最终位置，放入元素queue[k] = x;
}

2.1.4 堆化(heapify)的魔法

堆化是将一个无序数组转换成堆的过程。就像是一个混乱的公司，通过一系列的调整，最终形成了合理的层级结构：

// 从最后一个非叶子节点开始，依次向上进行堆化
for (int i = (size >>> 1) - 1; i >= 0; i--)siftDown(i);

这个过程的巧妙之处在于：

• 只需要处理非叶子节点
• 自底向上进行调整
• 每个节点最多下沉到叶子层
• 时间复杂度仅为O(n)

通过这些精妙的设计，我们用简单的数组就实现了一个高效的优先队列。这种实现方式：

• 节省内存空间
• 提高缓存命中率
• 操作效率高
• 实现简单优雅

这就是为什么PriorityQueue选择使用数组而不是链表来实现堆结构的原因。

2.2 关键操作的实现

在理解了堆的基本原理后，让我们来看看PriorityQueue中最常用的几个核心操作是如何实现的。这些操作就像是一个精心设计的舞蹈，每一步都恰到好处。

2.2.1 插入元素(offer)

插入操作就像是一个新员工加入公司后找到自己合适的位置：

public boolean offer(E e) {// 空值检查if (e == null)throw new NullPointerException();// 记录当前元素个数int i = size;// 检查是否需要扩容if (i >= queue.length)grow(i + 1);// 元素个数加1size = i + 1;// 如果是第一个元素，直接放入if (i == 0)queue[0] = e;else// 否则，执行上浮操作siftUp(i, e);return true;
}

这个过程包含：

• 参数校验
• 容量检查
• 位置确定
• 上浮调整

2.2.2 获取并删除堆顶元素(poll)

这就像是公司最高职位的人离职，需要重新选拔接班人：

public E poll() {// 如果堆为空，返回nullif (size == 0)return null;// 堆大小减1int s = --size;// 取出堆顶元素E result = (E) queue[0];// 取出最后一个元素E x = (E) queue[s];// 清空最后位置queue[s] = null;// 如果堆不为空，需要进行下沉操作if (s != 0)siftDown(0, x);return result;
}

关键步骤：

• 取出最大（小）元素
• 最后元素提升到顶部
• 进行下沉调整
• 维护堆的性质

2.2.3 查看堆顶元素(peek)

这是最简单的操作，就像看一眼公司的最高领导是谁：

public E peek() {return (size == 0) ? null : (E) queue[0];
}

特点：

• 不修改堆结构
• O(1)时间复杂度
• 返回但不删除元素

2.2.4 删除指定元素(remove)

这就像是公司中某个人离职，需要重新调整组织结构：

public boolean remove(Object o) {// 找到元素的位置int i = indexOf(o);if (i == -1)return false;// 堆大小减1int s = --size;// 如果是最后一个元素，直接删除if (s == i)queue[i] = null;else {// 否则，用最后一个元素替代，然后进行调整E moved = (E) queue[s];queue[s] = null;siftDown(i, moved);// 如果下沉后位置没变，可能需要上浮if (queue[i] == moved)siftUp(i, moved);}return true;
}

这个操作比较复杂：

• 需要先定位元素
• 可能需要下沉
• 可能需要上浮
• 要处理多种情况

通过这些操作的实现，我们可以看到：

• 每个操作都精心设计
• 保证了堆的性质
• 维护了优先级顺序
• 实现了高效的元素管理

这些操作共同构成了PriorityQueue的核心功能，让它能够高效地管理具有优先级的元素。

3. 源码分析

深入PriorityQueue的源码，就像拆解一台精密的机器，每个零件都有其独特的作用。让我们先来看看这台"机器"的核心部件。

3.1 核心属性和构造方法

3.1.1 核心属性

// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;// 存储元素的数组
transient Object[] queue;// 当前队列中的元素个数
private int size = 0;// 比较器
private final Comparator<? super E> comparator;// 修改次数（用于快速失败机制）
transient int modCount = 0;

这些属性的设计很有讲究：

1. 初始容量为什么是11？

• 不是2的幂次方，避免与其他数据结构混淆
• 足够小，避免空间浪费
• 足够大，避免频繁扩容
• 奇数便于堆的平衡

2. 为什么用Object[]而不是泛型数组？

• Java不支持直接创建泛型数组
• 需要在运行时进行类型转换
• 内部实现的技术选择

3. 为什么需要modCount？

• 实现快速失败机制
• 在并发修改时及时抛出异常
• 保证迭代器的一致性

3.1.2 构造方法

PriorityQueue提供了多个构造方法，满足不同场景的需求：

1. 默认构造

public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);
}

2. 指定容量

public PriorityQueue(int initialCapacity) {this(initialCapacity, null);
}

3. 指定比较器

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;
}

构造方法的设计体现了几个重要原则：

1. 参数校验

• 容量必须大于0
• 支持空比较器（使用自然顺序）

2. 重载设计

• 提供多种初始化方式
• 统一到一个核心构造方法
• 遵循DRY原则

3. 灵活性

• 可以自定义初始容量
• 可以自定义比较规则
• 可以使用默认配置

3.1.3 特殊构造方法

除了基本构造方法，还提供了基于其他集合的构造方法：

// 使用已有集合构造
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);}
}

这个构造方法展示了良好的设计思想：

• 充分利用已有数据结构的特性
• 优化不同场景下的初始化过程
• 保持堆的性质

通过这些属性和构造方法的设计，我们可以看到PriorityQueue在实现上的严谨和灵活。接下来，我们将深入探讨它的核心操作实现。

3.2 核心方法实现

在理解了基本属性和构造方法后，让我们来看看PriorityQueue中最常用的几个核心操作是如何实现的。这些操作就像是一个精心设计的舞蹈，每一步都恰到好处。

3.2.1 add/offer方法

虽然PriorityQueue提供了add和offer两个方法，但实际上add方法只是对offer的简单包装：

public boolean add(E e) {return offer(e);
}public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;if (i >= queue.length)grow(i + 1);siftUp(i, e);size = i + 1;return true;
}

这里的设计体现了几个关键点：

1. 空值处理：不允许插入null元素
2. 容量管理：自动扩容
3. 维护顺序：通过siftUp保持堆的性质
4. 并发控制：修改modCount以支持快速失败

3.2.2 扩容机制

当数组空间不足时，PriorityQueue会通过grow方法进行扩容：

private void grow(int minCapacity) {int oldCapacity = queue.length;// 如果旧容量小于64，容量翻倍// 如果旧容量大于等于64，容量增加一半int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));// 检查是否溢出if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);
}

扩容策略的精妙之处：

• 小容量时翻倍增长，避免频繁扩容
• 大容量时增加一半，避免内存浪费
• 考虑了数组大小的边界情况

3.2.3 删除操作

删除操作包括removeAt（内部方法）和remove（公共方法）：

private E removeAt(int i) {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) {siftUp(i, moved);if (queue[i] != moved)return moved;}}return null;
}

这个实现展示了：

• 特殊情况的处理（最后一个元素）
• 堆的重新平衡（可能需要上浮或下沉）
• 对并发修改的控制

3.2.4 查找操作

虽然优先队列主要用于维护优先级顺序，但有时也需要查找特定元素：

private int indexOf(Object o) {if (o != null) {for (int i = 0; i < size; i++)if (o.equals(queue[i]))return i;}return -1;
}

这个简单的实现告诉我们：

• PriorityQueue不是为查找设计的
• 查找操作是O(n)复杂度
• 如果需要频繁查找，应考虑其他数据结构

3.2.5 迭代器实现

PriorityQueue的迭代器实现也很有特色：

public Iterator<E> iterator() {return new Itr();
}private final class Itr implements Iterator<E> {private int cursor;private int lastRet = -1;private ArrayDeque<E> forgetMeNot;private E lastRetElt;private int expectedModCount = modCount;public boolean hasNext() {return cursor < size ||(forgetMeNot != null && !forgetMeNot.isEmpty());}public E next() {if (expectedModCount != modCount)throw new ConcurrentModificationException();if (cursor < size)return (E) queue[lastRet = cursor++];// ... 其他逻辑}
}

迭代器的设计考虑了：

• 并发修改检测
• 元素顺序的维护
• 遍历过程中的元素删除

通过这些核心方法的实现，我们可以看到PriorityQueue在设计上的严谨性和灵活性。每个方法都经过精心设计，既保证了功能的正确性，又兼顾了性能的优化。

写在最后

🎉 到这里，PriorityQueue优先队列详解的上篇就分享完啦！由于内容较多，我们把文章分成了上下两篇：

• 上篇（本篇）：重点讲解基础概念和源码分析
• 下篇：将深入探讨实战应用、性能优化和面试技巧，敬请期待！

如果觉得有帮助的话，别忘了点个赞 👍 收藏 ⭐ 关注 🔖 哦！

💡 开发路上，我们都是学习者。如果你有任何问题或更好的想法，欢迎在评论区留言交流！

🤝 一起进步，共同成长~

---

🎯 我是果冻~，一个热爱技术、乐于分享的开发者
📚 更多精彩内容，请关注我的博客
🌟 我们下期再见！