Java基础 | 优先队列PriorityQueue详解

橘生淮南2023-12-242024-03-14

一、快速使用指南

1.1 使用模板

new PriorityQueue<>(k,Comparator)

（可选）k表示初始容量，默认容量为11
（可选）Comparator为比较器，用于告诉编译器如何比较大小或者修改为大根堆（默认是小根堆）

1
2

PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val));
//这里定义比较器是明确如何比较两个ListNode的大小，否则编译器不知道如何比较。仍然是小根堆。

1.2 操作说明

1.2.1 增

方法	返回值	插入失败时抛出异常
add	无	是
offer	布尔型（boolean）	否，返回false

注意，不能插入null对象，否则会抛出NullPointerException

没有容量限制，可以插入任意多个元素，其内部可以自动扩容

实际上因为优先队列会自动扩容，队列不会满（除非硬盘空间不足），所以对于优先队列而言，add和offer没啥区别

1.2.2 删

出队：E poll()

清空：void clear()

1.2.3 查

查看是否为空：boolean isEmpty()

查看队列大小：int size()

查看队顶元素：E peek()

二、基本定义

队列是一种 先进先出(FIFO) 的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该种场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue) 。

三、底层实现

JDK1.8 中的 PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。因此可以按层序的规则采用顺序的方式来高效存储。

完全二叉树：如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左而右。则深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1 ，则它就是满二叉树。满二叉树是一种特殊的完全二叉树