PriorityQueue 数据结构底层原理、源码实现可视化分析及应用实战

炖炖發表於 2025-8-31 23:32:00

PriorityQueue 数据结构底层原理、源码实现可视化分析及应用实战

<blockquote>
本文将从数据结构底层原理 + 源码实现 + 应用实战三方面深入剖析 <code>PriorityQueue</code>，让你真正掌握优先队列的底层逻辑及其应用。
源码可视化视频：https://www.bilibili.com/video/BV12Ha5zjEcS/
</blockquote>
在玩游戏的时候，发现需要购买的装备很多，而且不同的英雄需要购买的装备还不一样，打游戏的时候需要更多精力去关注买什么装备才行。这多少影响游戏体验，特别是我这种小白，打开装备栏挑了半天没找到自己要买的，然后就嘎了^。游戏难度太大（体验太差）玩不来，卸载了吧。
如果开始游戏前就先配置好我要玩的英雄的装备购买顺序，那岂不美哉。打游戏的时候，游戏自动提示你要购买的装备，直到你全部装备都买好了。
通过<code>PriorityQueue</code>便可轻松实现上面想要的功能。
<blockquote>
开始游戏前配置装备优先级的过程为：入队操作过程；
打游戏提示购买装备顺序的过程为：出队操作过程。
</blockquote>
文中实战部分会讲到这个案例如何实现，我们先从最简单的是什么开始。
<h2 id="-1-概述">🚀 1. 概述</h2>
<h3 id="11-priorityqueue-是什么">1.1. PriorityQueue 是什么？</h3>
<code>PriorityQueue</code> 是一个 优先级的队列，元素按优先级从小到大排列（默认使用自然顺序，也可以传入比较器 Comparator）。
它并不保证 FIFO 顺序，也不保证整个队列有序，而是每次出队时返回当前优先级最高的元素。说白了，仅保证每次出队的元素是最大值或最小值，默认是最小值。
<h3 id="12-底层数据结构">1.2. 底层数据结构</h3>
<code>PriorityQueue</code> 使用一个动态数组来维护数据，底层处理逻辑为二叉堆，默认为小顶堆。
学习<code>PriorityQueue</code>底层原理，就是学习怎么应用二叉堆实现优先队列。
二叉堆为完全二叉树，按照从上到下、从左到右的顺序进行入堆，并且仅有最底层可能没有填满。
假设当前堆如下（<code>PriorityQueue</code> 数组下标从 0 开始）：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230417102-1258248651.jpg" alt="PriorityQueue层次遍历" loading="lazy">
在数组中的保存顺序为二叉树的层序遍历顺序：从根节点开始，从上到下、从左到右一个个遍历。
所以在数组表示为：<code></code>
<h3 id="13-二叉堆的规律">1.3. 二叉堆的规律</h3>
这些规律将决定你的代码怎么去实现。
<code>PriorityQueue</code>的下标<code>i</code>是从<code>0</code> 开始计算的，以下公式也是基于<code>i=0</code>才成立的。
规律1，根据父节点计算子节点：父节点下标 <code>i</code>，那么左子节点就为 <code>2*i+1</code>，右子节点为 <code>2*i+2</code>。
反过来，如果左子节点为<code>i</code>，那么父节点为<code>(i-1)/2</code>；如果右子节点为<code>i</code>，那么父节点为<code>(i-2)/2</code>;
计算父结点一定要两个公式？？
左右节点相差<code>1</code>，必然会有一个是不能整除。
比如：左节点<code>i=1</code>,那么右节点必为<code>i=2</code>，父节点为<code>0</code>。
如果使用公式<code>(i-1)/2</code>，那么左节点计算结果为<code>0</code>，右节点计算为<code>0.5</code>，只需要向下取整即可。
如果使用公式<code>(i-2)/2</code>，那么左节点计算结果为<code>-0.5</code>，右节点计算为<code>0</code>，发现怎么取整都不可以。
规律2，根据子节点计算父节点：使用公式<code>(i-1)/2</code>计算并向下取整即可。
规律3，小顶堆/最小堆的每个节点都比它的子节点小；大顶堆/最大堆的每个节点都比它的子节点大。
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230432496-1008503043.jpg" alt="PriorityQueue规律" loading="lazy">
<h2 id="️-2-入队相关操作">⚙️ 2. 入队相关操作</h2>
上面的规律如果明白了，那下面的源码就很好明白了。
<h3 id="21-入队操作">2.1. 入队操作</h3>
先明确知道，插入节点的入堆顺序是按照层序遍历从上到下、从左到右，就像你写作文一样从左到右➡，从上到下⬇地编写，也就是每次都放在数组元素的末端。
再结合小顶堆规律和二叉堆的计算公式：由子得父的简单计算公式。
涉及的关键源码：<code>offer(e)</code> 和 <code>siftUp</code>。
<pre><code class="language-java">// 入队操作
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
// 容量满后才扩容
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue = e;
else
siftUp(i, e);
return true;
}
// siftUp 上浮
private void siftUp(int k, E x) {
if (comparator != null)
// 使用了自定义比较器
siftUpUsingComparator(k, x);
else
// 使用类中的比较器
siftUpComparable(k, x);
}
// siftUp 源码逻辑（有 Comparator 时）
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
// 由子节点计算出父节点数组索引
int parent = (k - 1) >>> 1;
// 获取父节点对象
Object e = queue;
// 比较大小：儿子>=父亲就没得玩了
if (comparator.compare(x, (E) e) >= 0)
break;
// 儿子低位还小，继续上位，把老父亲换下去
queue = e;
// 更新索引，继续比较
k = parent;
}
// 最终看实力上位到 k 位置，坐好
queue = x;
}
</code></pre>
使用了规律2（公式<code>(i-1)/2</code>计算，并向下取整），根据子节点计算父节点索引。
但源码的计算公式为：<code>parent = (k - 1) >>> 1</code>。
源码采用无符号右移一位，相当于除于2，但位移运算余数不会被保存，也就无需向下取整
比如：<code>k=4</code>，那么<code>k-1=3</code>，3 的二进制为<code>11</code>，右移一位变为<code>1</code>。
位移运算只会有整数部分参与运算，结果也只会有整数部分。
入队操作动图：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230453973-1911214891.gif" alt="入队操作" loading="lazy">
<h3 id="22-扩容操作">2.2. 扩容操作</h3>
底层数据结构为数组，扩容操作跟<code>ArrayList</code> 基本一致。
扩容操作很简单，主要分为两步：计算新容量和元素拷贝。
<code>Priority</code>和<code>ArrayList</code>的扩容主要区别为：容量计算有一点点差异。
在容量小于64前，<code>Priority</code> 扩容的新容量为：翻倍+2；后面的扩容都一致为：增加 50%容量。增长量 = <code>oldCapacity >> 1</code>，即 <code>oldCapacity/2</code>（向下取整）。
具体源码如下：
<pre><code class="language-java">// 扩容
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 计算新容量
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// 防止溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 拷贝元素到新数组
queue = Arrays.copyOf(queue, newCapacity);
}
// 防止溢出
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
</code></pre>
<h2 id="-3-出队操作">🗑 3. 出队操作</h2>
出队操作分为三步：取堆顶，替堆顶，沉堆顶
取出堆的根节点--堆顶，即数组的第一个元素；
然后用最后一个节点替代堆顶；
堆顶下沉操作，最后取左右子节点最小的跟父节点比较，父大于子，则交换节点，完成堆顶下沉。
具体源码如下：
<pre><code class="language-java">// 出队操作
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
// 取出堆顶
E result = (E) queue;
// 用最后一个元素替代堆顶
E x = (E) queue;
// 移除最后一个节点
queue = 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 siftDownUsingComparator(int k, E x) {
// 大小除于2，half 为第一个叶子节点
int half = size >>> 1;
// k 不是叶子节点，才需要上浮
while (k < half) {
// 由父得子：此为左节点公式
int child = (k << 1) + 1;
Object c = queue;
// 左加一，得右节点索引
int right = child + 1;
// 左右节点比较，取小的节点
if (right < size &&
comparator.compare((E) c, (E) queue) > 0)
c = queue;
// 小儿子和冒牌顶替的父亲比较
if (comparator.compare(x, (E) c) <= 0)
break;
// 下沉交换
queue = c;
k = child;
}
// 保存到合适的位置
queue = x;
}
</code></pre>
PriorityQueue 就是通过出队的方式实现优先级的。它可以只出队一部分，完成部分优先级操作；也可以全部都出队，此时出队结果便是堆排序结果。
认真看下源码，有没有发现什么端倪？？
为什么循环条件是<code>while (k < half) </code>？
因为所有叶子节点都没有孩子，也就没有可以在下沉可说了。
出队操作动图：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230533424-560852651.gif" alt="出队操作" loading="lazy">
<h2 id="️-4-批量建堆heapify">🏗️ 4. 批量建堆（heapify）</h2>
现在有n个元素，通过入队操作，一个个放入数组中，单个元素操作的时间复杂度为<code>O(logn)</code>，n 个元素的时间复杂度就变为<code>O(n*logn)</code>。
现在有个更高效的方式：批量建堆。当已有一整个数组时，采用一次建堆，时间复杂度为<code>O(n)</code>
批量建堆就像盖房子一样，从地基开始，一层一层的搭建好。
批量建堆的整体过程：自底向上、逐层建堆
详细的处理过程为：
<ol>
<li>先将元素直接全部拷贝到数组</li>
<li>再从最后一个非叶子节点开始逆层序遍历建堆，</li>
<li>对每个子树的堆顶节点做下沉操作，保证其子树满足小顶堆特性</li>
</ol>
当通过带初始集合的构造器创建 <code>PriorityQueue</code> 时，会执行一次 批量建堆，其核心代码在构造器末尾调用：
<pre><code class="language-java">public PriorityQueue(Collection<? extends E> c) {
// … 将 c.toArray() 填充到 queue[]
this.size = queue.length;
heapify();
}
</code></pre>
<h3 id="41-heapify-源码逻辑">4.1. heapify 源码逻辑</h3>
<pre><code class="language-java">private void heapify() {
int n = size;
// 从最后一个非叶子节点开始，依次向下调整
for (int i = (n >>> 1) - 1; i >= 0; i--) {
 siftDown(i, (E) queue);
}
}
</code></pre>
这源码可能看得有点费劲，这样可能清晰点
<pre><code class="language-java">private void heapify() {
// 找到最后一个非叶节点
int lastParent = (size >>> 1) - 1;
// 从这个节点开始，往前遍历到根节点
for (int i = lastParent; i >= 0; i--) {
 // 把 queue “下沉”到它在子树中正确的位置
 siftDown(i, (E) queue);
}
}
</code></pre>
开始位置：由完全二叉树二叉堆的特性，可知最后一个非叶子节点下标为 <code>(size >>> 1) - 1</code>，这个索引往后的节点都是叶子节点，无需调整。
建堆过程：对每个节点调用 <code>siftDown</code>，保证其子树满足最小堆性质
建堆索引顺序图：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230555083-1490702394.jpg" alt="PriorityQueue建堆索引移动顺序" loading="lazy">
黄色三角形内只需要一次调平就可完成，然后继续往上逐层调整：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230604715-200444042.jpg" alt="PriorityQueue建堆调平1" loading="lazy">
最后调整完成：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230614037-1132620840.jpg" alt="PriorityQueue建堆调平2" loading="lazy">
整个建堆过程为：从最后非叶子节点开始，自底向上，逐个下沉调整，直到堆顶。
批量建堆可视化：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230640052-1719357637.gif" alt="批量建堆操作" loading="lazy">
哪可不可以从堆顶开始调整，自顶向下，逐层下沉调整？
<h3 id="42-为什么自底向上更快">4.2. 为什么自底向上更快？</h3>
如果采用从堆顶开始调整，自顶向下，逐层下沉调整会怎样？
<h4 id="421-为什么选择自底向上逐层下沉">4.2.1. 为什么选择自底向上、逐层下沉？</h4>
❌从堆顶开始调整，自顶向下，逐层下沉调整。当你在 <code>i=0</code>（根节点）做 <code>siftDown</code> 时，左右子树尚未调整，它们可能不是堆。尽管上层节点调整好了，之后再去调整下层节点时，又可能会破坏你先前在上层建立的堆序性，最终很可能得到一个不合法的堆。如果要确保每层都合法，那就得重复计算上层已经调整好的堆，重复计算导致性能低下。
✅顺着不行只能“逆天而行”，自底向上、逐层建堆。从最后一个非叶子节点开始建堆，那它的左右孩子必为叶子节点，叶子节点相当于已经建好的堆。逐层往上，当你在父节点 <code>i</code> 上调用 <code>siftDown</code> 时，它的左右子树都已经是堆了（因为你先处理好更深层的节点）。这样，单次 <code>siftDown</code> 只需要把第 <code>i</code> 个节点“插入”到一个已经是堆的子树里，最终整棵树就成为堆。
<blockquote>
相当于已经计算好的结果，可以应用到后面的计算，从而避免不必要的重复计算，大大提高建堆性能。
在线性时间内、一步到位地把数组“堆化”
</blockquote>
<h4 id="422-计算建堆时间复杂度">4.2.2. 计算建堆时间复杂度</h4>
建堆总工作量分析计算：
在批量 heapify 中，只有非叶节点会执行下沉。完美二叉树上共有约 <code>n/2</code> 个非叶节点。
那么，可以下沉至少 1 层 的节点最多有多少呢？
<blockquote>
最多是所有非叶节点都可以下沉1层，一共<code>≤ n/2</code>次单步下沉
</blockquote>
可以下沉至少 2 层 的节点最多有多少？
<blockquote>
只有距叶子深度 ≥2 的节点，一共 <code>≤n/4</code>次单步下沉
</blockquote>
可以下沉至少 3 层 的节点数最多有多少？
<blockquote>
只有距叶子深度 ≥3 的节点，一共 <code>≤n/8</code>次单步下沉
</blockquote>
...
一直到堆顶，可能的最大下沉深度k层，一共 <code>≤n/2^k</code>次单步下沉
总单步下沉数 
把“下沉至少 k 层”的所有单步加起来，就是下沉总次数
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230951593-1228154433.jpg" alt="时间复杂度计算" loading="lazy">
元素拷贝： 将整个数组元素直接拷贝到内部 <code>queue</code> 数组，时间复杂度<code>O(n)</code>；
最终总工作量=元素拷贝 + 建堆的时间复杂度=<code>O(n) + O(n) = O(n)</code>
批量建堆时间复杂度计算可视化：
<img src="https://img2024.cnblogs.com/blog/1209017/202508/1209017-20250831230810145-1196529873.gif" alt="批量建堆时间复杂度计算" loading="lazy">
对比入队和建堆的时间复杂度：
<table>
<thead>
<tr>
<th>方法</th>
<th>时间复杂度</th>
<th>何时使用</th>
</tr>
</thead>
<tbody>
<tr>
<td>入队＋siftUp</td>
<td>O(n log n)</td>
<td>动态地一个个插入元素</td>
</tr>
<tr>
<td>一次性 heapify＋siftDown</td>
<td>O(n)</td>
<td>已有一整个数组，一次建堆</td>
</tr>
</tbody>
</table>
<h2 id="-5-应用实战">💡 5. 应用实战</h2>
<h3 id="51-小顶堆">5.1. 小顶堆</h3>
默认就是小顶堆
<pre><code class="language-java">PriorityQueue<String> priorityQueue = new PriorityQueue<>();
priorityQueue.offer("1");
priorityQueue.offer("5");
priorityQueue.offer("3");
priorityQueue.offer("7");
priorityQueue.offer("9");

System.out.println(priorityQueue);

priorityQueue.poll();

System.out.println(priorityQueue);
</code></pre>
测试结果：
<pre><code>

</code></pre>
<h3 id="52-大顶堆">5.2. 大顶堆</h3>
想实现最大堆？传入 Comparator 即可：
<pre><code class="language-java">PriorityQueue<String> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer("1");
maxHeap.offer("5");
maxHeap.offer("3");
maxHeap.offer("7");
maxHeap.offer("9");
System.out.println(maxHeap);

maxHeap.poll();

System.out.println(maxHeap);
</code></pre>
测试结果
<pre><code>

</code></pre>
<h3 id="53-比较器">5.3. 比较器</h3>
堆内元素为自定义对象<code>Person</code>，实现 默认按年龄降序 排序（即年龄越大优先）
具体源码如下：
<pre><code class="language-java">public class Person implements Comparable<Person>{
private String name;
private Integer age;

public String getName() {
 return name;
}

public void setName(String name) {
 this.name = name;
}

public Integer getAge() {
 return age;
}

public void setAge(Integer age) {
 this.age = age;
}

public Person(String name, Integer age) {
 this.name = name;
 this.age = age;
}
@Override
public int compareTo(Person other) {
// return this.age.compareTo(other.age);// 小顶堆：按年龄升序
 // 大顶堆：降序：年龄大的排前面
 return other.age.compareTo(this.age);
}

@Override
public String toString() {
 return name + " (" + age + ")";
}

public static void main(String[] args) {
 PriorityQueue<Person> personPriorityQueue = new PriorityQueue<>();
 personPriorityQueue.offer(new Person("张三",28));
 personPriorityQueue.offer(new Person("李四",21));
 personPriorityQueue.offer(new Person("渊渟岳",18));
 personPriorityQueue.offer(new Person("咿呀呀",19));
 System.out.println(personPriorityQueue);
}

}
</code></pre>
执行结果：
<pre><code>[张三 (28), 李四 (21), 渊渟岳 (18), 咿呀呀 (19)]
</code></pre>
同样可以对它做取反操作，变为小顶堆，从小到大的年龄排序
<pre><code class="language-java">PriorityQueue<Person> personPriorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
personPriorityQueue.offer(new Person("张三",28));
personPriorityQueue.offer(new Person("李四",21));
personPriorityQueue.offer(new Person("渊渟岳",18));
personPriorityQueue.offer(new Person("咿呀呀",19));
System.out.println(personPriorityQueue);
</code></pre>
执行结果：
<pre><code>[渊渟岳 (18), 咿呀呀 (19), 李四 (21), 张三 (28)]
</code></pre>
<h3 id="54-找出年龄最大的前-k-个人">5.4. 找出年龄最大的前 K 个人</h3>
我们来实现一个典型的 Top-K 最大年龄的 Person 问题。
实现思路：
使用 <code>PriorityQueue<Person></code>，保存堆顶为当前第 K 大的元素，大小为 K；
遍历所有元素：如果堆未满：加入；如果堆满，且当前元素年龄大于堆顶：替换堆顶；
最终堆中就是 Top-K 最大年龄的 Person。
具体源码如下：
<pre><code class="language-java">public class TopKDemo {
/**
* 获取数组中前 K 个最小或最大的元素
*这里实现的是前 K 个年龄大的
*/
public static List<Person> getTopKByAge(List<Person> people, int k) {
 if (people == null)
 throw new RuntimeException("家里没有人");
 // 小顶堆：堆顶是当前 Top-K 里最小年龄的，因为Person类是正序排序
 PriorityQueue<Person> minHeap = new PriorityQueue<>(k);

 for (Person p : people) {
 if (minHeap.size() < k) {
 minHeap.offer(p);
 }
 // 堆满 K 个元素后，取堆顶判断元素大小
 else if (p.compareTo(minHeap.peek())>0) {
 minHeap.poll();
 minHeap.offer(p);
 }
 }
 // 转换回 List
 List<Person> result = new ArrayList<>(minHeap);
 return result;
}

public static void main(String[] args) {
 // 测试数据
 List<Person> people = Arrays.asList(
 new Person("张三", 28),
 new Person("李四", 21),
 new Person("渊渟岳", 18),
 new Person("咿呀呀", 19),
 new Person("王五", 33),
 new Person("老六", 33)
 );

 int k = 3;
 List<Person> topK = getTopKByAge(people, k);
 System.out.println("Top " + k + " 最老的人:");
 topK.forEach(System.out::println);
}
}
</code></pre>
执行结果
<pre><code>Top 3 最老的人:
张三 (28)
王五 (33)
老六 (33)
</code></pre>
这里容易搞错的点是：大顶堆和小顶堆的选择上。
<blockquote>
取前K个最大元素，得选用小顶堆，这样才能确保每次比较大小时，都是和堆内最小的元素进行比较，取出最小的，留下最大的元素在堆内。
</blockquote>
<code>PriorityQueue</code> 适用于：取数组前 K 个最小或最大的元素
<h3 id="55-购买游戏装备问题">5.5. 购买游戏装备问题</h3>
先定义一个购买装备的配置对象，用来保持配置优先级信息，规定<code>priority</code> 数字越小优先购买。
<pre><code class="language-java">public class EquipmentItem implements Comparable<EquipmentItem> {
private final String name;
private final int priority; // 数字越小优先购买

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

public String getName() {
 return name;
}

@Override
public int compareTo(EquipmentItem other) {
 return Integer.compare(this.priority, other.priority);
}

@Override
public String toString() {
 return String.format("%s (priority=%d)", name, priority);
}
}
</code></pre>
接着完成管理单个英雄的装备购买顺序
<pre><code class="language-java">/**
* 管理单个英雄的装备购买顺序
*/
public class HeroEquipmentPlan {
private final String heroName;
private final PriorityQueue<EquipmentItem> planQueue = new PriorityQueue<>();

public HeroEquipmentPlan(String heroName) {
 this.heroName = heroName;
}

/**
* 预先设置一系列装备及其优先级
*/
public void addItem(String itemName, int priority) {
 planQueue.offer(new EquipmentItem(itemName, priority));
 System.out.println("添加装备到购买计划: " + itemName + "，优先级为：" + priority);
}

/**
* 获取下一个最优先购买的装备
*/
public EquipmentItem getNextItem() {
 EquipmentItem next = planQueue.poll();
 if (next == null) {
 System.out.println("全部购买完成：" + heroName);
 } else {
 System.out.println("下一个购买项：" + heroName + ": " + next);
 }
 return next;
}

/**
* 查看当前购买计划（不移除）
*/
public void previewPlan() {
 System.out.println("当前购买计划：" + heroName + ":");
 planQueue.stream()
 .sorted()
 .forEach(item -> System.out.println("- " + item));
}

}
</code></pre>
测试装备购买顺序配置，再进行装备购买
<pre><code class="language-java">public class Demo{
public static void main(String[] args) {
 // 游戏开始前：为英雄设置购买优先级
 HeroEquipmentPlan plan = new HeroEquipmentPlan("战士");
 plan.addItem("长剑", 1);
 plan.addItem("护甲", 2);
 plan.addItem("靴子", 3);
 plan.addItem("暴击手套", 4);
 plan.addItem("巨人腰带", 5);

 // 开局预览
 plan.previewPlan();

 // 游戏中：当有足够金币时，依次购买下一个装备
 EquipmentItem next;
 while ((next = plan.getNextItem()) != null) {
 // 在这里调用游戏购买接口或提醒玩家：
 // buyItem(next.getName());
 // 模拟购买间隔
 try {
 Thread.sleep(2000);
 } catch (InterruptedException ignored) {}
 }

 System.out.println("购买计划已完成，祝游戏愉快！");
}
}
</code></pre>
测试结果:
<pre><code>添加装备到购买计划: 长剑，优先级为：1
添加装备到购买计划: 护甲，优先级为：2
添加装备到购买计划: 靴子，优先级为：3
添加装备到购买计划: 暴击手套，优先级为：4
添加装备到购买计划: 巨人腰带，优先级为：5
当前购买计划：战士:
- 长剑 (priority=1)
- 护甲 (priority=2)
- 靴子 (priority=3)
- 暴击手套 (priority=4)
- 巨人腰带 (priority=5)
下一个购买项：战士: 长剑 (priority=1)
下一个购买项：战士: 护甲 (priority=2)
下一个购买项：战士: 靴子 (priority=3)
下一个购买项：战士: 暴击手套 (priority=4)
下一个购买项：战士: 巨人腰带 (priority=5)
全部购买完成：战士
购买计划已完成，祝游戏愉快！
</code></pre>
<code>PriorityQueue</code> 适用于：管理优先级任务调度
<h2 id="-6-汇总">📈 6. 汇总</h2>
<h3 id="61-时间复杂度汇总">6.1. 时间复杂度汇总</h3>
<table>
<thead>
<tr>
<th>操作</th>
<th>时间复杂度</th>
</tr>
</thead>
<tbody>
<tr>
<td>入队 offer()</td>
<td>O(log n)</td>
</tr>
<tr>
<td>出队 poll()</td>
<td>O(log n)</td>
</tr>
<tr>
<td>访问 peek()</td>
<td>O(1)</td>
</tr>
<tr>
<td>建堆 heapify</td>
<td>O(n)</td>
</tr>
<tr>
<td>循环入队式建堆</td>
<td>O(n log n)</td>
</tr>
</tbody>
</table>
<h3 id="62-常见误区">6.2. 常见误区</h3>
<table>
<thead>
<tr>
<th>误区</th>
<th>正解</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>PriorityQueue</code> 是 FIFO？❌</td>
<td>✅ 它默认是最小堆，优先出最小元素</td>
</tr>
<tr>
<td>删除元素快？❌</td>
<td>✅ 仅堆顶是 O(log n)，任意删除是 O(n)</td>
</tr>
<tr>
<td>支持 null 元素？❌</td>
<td>✅ 不允许插入 null，会抛异常</td>
</tr>
<tr>
<td>是线程安全的吗？❌</td>
<td>✅ 需要手动加锁或使用线程安全版本<code>PriorityBlockingQueue</code></td>
</tr>
</tbody>
</table>
<h2 id="-7-总结">📚 7. 总结</h2>
二叉堆就四句话：有批量选批量，没批量逐个建；获取最优数值，重建合法堆形。
PriorityQueue 优先队列和普通的二叉堆一样，主要分为三部分：初建堆、取最值、重建堆。其中建堆分为两种情况：逐个入队建堆和批量建堆。
<code>PriorityQueue</code> 是建立在小顶堆结构上的非线程安全队列，底层数据结构为数组，核心处理逻辑为二叉堆，通过 <code>siftUp</code> 和 <code>siftDown</code> 动态维护堆结构，默认最小堆，但可以通过 Comparator 灵活定制。
适合优先级任务调度、动态最值维护、Top-K等场景。注意线程安全与迭代顺序的问题，在并发场景下使用 <code>PriorityBlockingQueue</code>。
<h2 id="往期推荐">往期推荐</h2>
<table>
<thead>
<tr>
<th>分类</th>
<th>往期文章</th>
</tr>
</thead>
<tbody>
<tr>
<td>Java集合底层原理可视化</td>
<td>Java 集合--快速掌握涵盖三大场景实现的Set集合底层原理 ArrayDeque双端队列--底层原理可视化 “子弹弹夹”装弹和出弹的抽象原理实战：掌握栈的原理与实战 TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？ LinkedHashMap集合--原理可视化 HashMap集合--基本操作流程的源码可视化 Java集合--HashMap底层原理可视化，秒懂扩容、链化、树化 Java集合--从本质出发理解HashMap Java集合--LinkedList源码可视化 Java集合源码--ArrayList的可视化操作过程</td>
</tr>
<tr>
<td>设计模式秘籍 （已全部开源）</td>
<td>掌握设计模式的两个秘籍 往期设计模式文章的：设计模式</td>
</tr>
<tr>
<td>软件设计师</td>
<td>软考中级--软件设计师毫无保留的备考分享 软件设计师--案例分析题轻松上分，解决你的备考烦恼 通过软考后却领取不到实体证书？ 2023年下半年软考考试重磅消息</td>
</tr>
<tr>
<td>Java学习路线 和相应资源</td>
<td>Java全栈学习路线、学习资源和面试题一条龙</td>
</tr>
</tbody>
</table>
原创不易，觉得还不错的，三连支持：点赞、分享、推荐↓ 
来源：https://www.cnblogs.com/dennyLee2025/p/19067516

頁: [1]

琼殿技术论坛's Archiver

PriorityQueue 数据结构底层原理、源码实现可视化分析及应用实战