PriorityQueue定义
PriorityQueue是Java集合框架中的一个实现了Queue接口的类，是 Java 中基于优先级的队列的通用实现。
PriorityQueue特点
PriorityQueue具有如下特点：
- PriorityQueue是一个基于优先级的队列，可以自动将元素按照指定的比较规则进行排序。
- PriorityQueue的底层实现是一个堆（Heap），默认是小根堆（即根节点最小）。
- PriorityQueue不允许插入null元素，并且元素必须实现Comparable接口。
- PriorityQueue的插入和删除元素的时间复杂度为O(logN)，其中N为队列的大小。
PriorityQueue原理
PriorityQueue的底层实现是基于堆（Heap）数据结构的，是通过完全二叉树（complete binary tree）实现的小顶堆。
如下图所示：
堆是一种特殊的二叉树，满足以下两个性质：
- 堆序性质（Heap Property）：对于堆中的每一个节点，它的值必须大于（或小于）它的子节点的值。
- 完全二叉树性质（Complete Binary Tree Property）：堆必须是一棵完全二叉树，也就是说除了最后一层之外，其他层的节点都必须是满的。
堆分为大根堆和小根堆，它们的区别在于根节点的值，在大根堆中，根节点的值最大，而在小根堆中，根节点的值最小，PriorityQueue默认是小根堆。
PriorityQueue中每个元素都是一个节点，节点之间是按照完全二叉树的形式排列的。
为了满足堆序性质，PriorityQueue维护了一个二叉堆结构，并对元素进行排序。
PriorityQueue使用
1.PriorityQueue常用方法
- 插入元素：可以使用offer()或add()方法来插入元素，如果元素超过了队列的容量，PriorityQueue会自动扩容。
- 删除元素：可以使用poll()或remove()方法来删除队头元素，这会将队头元素从队列中删除并返回它。
- 查看队头元素：可以使用peek()方法来查看队头元素，但是不会从队列中删除它。
- 判断队列是否为空：可以使用isEmpty()方法来判断队列是否为空。
|
方法 |
说明 |
|
add(E e) |
添加元素，如果超过队列长度，抛出异常 |
|
offer(E e) |
添加元素，如果超过队列长度返回false |
|
remove() |
获取下个元素，如果没有抛出异常 |
|
poll() |
获取下个元素，如果没有返回null |
|
element() |
查看下个元素的内容，如果没有抛异常 |
|
peek() |
查看下个元素的内容，如果没有返回null |
2.PriorityQueue使用示例
PriorityQueue使用跟普通队列一样，唯一区别是PriorityQueue会根据排序规则决定谁在队头，谁在队尾。
如下所示：
import java.util.*;
public class PriorityQueueExample {
public static void main(String[] args) {
// 创建一个默认的小根堆PriorityQueue
PriorityQueue pq = new PriorityQueue<>();
// 插入元素
pq.offer(3);
pq.offer(1);
pq.offer(2);
// 删除元素
System.out.println(pq.poll()); // 输出1
// 查看队头元素
System.out.println(pq.peek()); // 输出2
// 判断队列是否为空
System.out.println(pq.isEmpty()); // 输出false
}
}
以上就是PriorityQueue的详解，更多Java集合框架，请查看：Java集合框架详解(看这篇就够了)。
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》