Java集合Queue-PriorityQueue
优先队列有两种：最大优先队列，当前最大的元素优先出队；最小优先队列，当前最小的元素优先出队。
PriorityQueue 通过用数组表示的小顶堆来实现，具体结构如下图所示
文章图片
首先任何结点都小于其左右子结点，除此之外，对于任何一个结点，假设它的下标为n：
- 左子结点：2 * n + 1
- 右子结点：2 * n + 2
- 父结点：(n + 1) / 2
- 成员变量
文章图片
- 构造函数
文章图片
看起来有7种实际上只有4种
文章图片
除了第一种，其它的是对PriorityQueue、SortedSet和其它Collection进行初始化，其中SortedSet本身就已经是排好序，所以不需要经过什么特殊处理，而其它的则需要调用heapify()进行处理。
文章图片
进入heapify()源码可以看到用到了siftDown()函数，后面会讲到
文章图片
文章图片
add 和offer 的语义是相同的，add也是调用了offer ，主要的是扩容函数grow 和筛选函数siftUp 。扩容函数后面讲，先来分析筛选函数(siftUp/siftDown)。
文章图片
文章图片
假设待插入的元素是4，这个gif图有个缺陷就是，比较完后，并不是4和待比较的结点交换，而是单纯把父节点移下来。
3 删除
文章图片
siftDown 和siftUp 差不多，都是包含有比较器和没有比较器两种方法，这里就拿一个分析即可。
文章图片
文章图片
文章图片
4 查询
由于查询并没有涉及结构的变化和调整，所以源码是非常简单的。
文章图片
5 扩容
扩容发生在添加元素的时候，当
size >= queue.length 的时候就会发生扩容。【Java集合Queue-PriorityQueue】
文章图片
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 图书集合完毕
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用（一）
- java之static、static|java之static、static final、final的区别与应用