[PriorityQueue/Java]PriorityQueue(优先队列)

1. 堆(Heap)、完全二叉树、堆排序

1.1 堆(Heap)的定义

从堆的定义可以看出，堆的实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点

1.2 完全二叉树

树中的结点按从上大小，一层一层，每层从左到右来编号。

1.3 堆排序

若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重新又建成一个堆，则得到n个元素的次小值（次大值）…如此反复，便能得到一个有序序列，这个过程称之为堆排序。

2. PriorityQueue(优先队列)

• 优先队列是堆排序的应用。
  小根堆实现最小优先队列
  大根堆实现最大优先队列

• 普通队列特点：First-In-First-Out（FIFO） 先进先出

• 优先队列：

  1. 最小优先队列，不管入队列顺序如何，当前最小的元素优先出队列；
  2. 最大优先队列，不管入队列顺序如何，当前最大的元素优先出队列；

• 可以用堆(Heap)来实现优先队列

  • 入队操作：每一次入队列就是一次堆的插入操作：在二叉树最后插入入队结点，进行结点调整，使其“上浮”至合适位置。
  • 出队操作：每一次出队列就是一次堆的删除堆顶结点操作，其实就是堆的调整：堆顶元素“出队”，以堆中最后一个元素代替之，不断“筛选”至得到新的堆。

• 以小根堆为例，示意堆(Heap)的入队和出队
  入队操作：不断上浮至合适位置
  
  出队操作：不断下滤至合适位置
  

• 小根堆的堆顶是整个堆中的最小元素，即可用小根堆实现最小优先队列
  大根堆的堆顶是整个堆中的最大元素，即可用大根堆实现最大优先队列

• PriorityQueue 初始容量为 11，支持动态扩容。容量小于 64 时，扩容一倍；大于 64 时，扩容 0.5 倍。

3. PriorityQueue常用方法

① boolean isEmpty()： 判断队列是否为空

② boolean add(E e)： 将指定元素插入到此优先队列中
③ boolean offer(E e)：将指定元素插入到此优先队列中
add()和offer()方法的语义完全相同，都是将指定元素插入到此优先队列中。区别在于当方法失败时前者抛出异常，后者返回false。对于PriorityQueue这两个方法没啥差别。
底层实现：由于新加入的元素可能会破坏堆的性质，需要将入队元素（在二叉树最后插入入队结点）“上浮”至合适位置。
时间复杂度：$O(logN)$

④ E element() ：获取但不删除此队列的首元素，如果此队列为空，则抛出异常
⑤ E peek() ：获取但不删除此队列的首元素，如果此队列为空，则返回null
element()和peek()方法的语义完全相同，都是获取但不删除此队列的首元素。区别在于当方法失败时前者抛出异常，后者返回null。
底层实现：由于堆用数组表示，可以根据下标，下标为0的元素即为堆顶元素，即返回数组索引为0的元素即可。
时间复杂度：$O(1)$

⑥ E remove()：获取并删除此队列的首元素，如果此队列为空，则抛出异常
⑦ E poll() ：获取并删除此队列的首元素，如果此队列为空，则返回null
remove()和poll()方法的语义完全相同，都是获取并删除此队列的首元素，区别是当方法失败时前者抛出异常，后者返回null。
底层实现：由于删除操作会改变队列的结构，为维护堆的性质，需要进行堆的调整：堆顶元素“出队”，以堆中最后一个元素代替之，不断“筛选”至得到新的堆。
时间复杂度：$O(logN)$

⑧ E remove(Object o)：删除此指定元素的单个实例（如果存在）。即删除此队列中和o相等的某一个元素（如果存在多个相等，则只删除一个）。
底层实现：由于删除操作会改变队列的结构，为维护堆的性质，需要进行堆的调整：堆顶元素“出队”，以堆中最后一个元素代替之，不断“筛选”至得到新的堆。又由于删除元素的位置是任意的，所以调整过程较为繁琐，可分为：1. 若删除的是最后一个元素，直接删除即可。2. 若删除的不是最后一个元素，以删除结点为首元素的子堆进行堆的调整。
时间复杂度：$O(N)$

• 想详细了解PriorityQueue底层实现原理的读者，可参考此文：PriorityQueue的用法和底层实现原理

• PriorityQueue相关代码及LeetCode题解，可详见此文：[LeetCode/PriorityQueue/Java]LeetCode之Heap(PriorityQueue)题解(Java)

本文地址：https://blog.csdn.net/KKKKKKOBE_24/article/details/109151413