JDK源码——PriorityQueue类

摘要

PriorityQueue其实是一个优先队列，和先进先出（FIFO）的队列的区别在于，优先队列每次出队的元素都是优先级最高的元素。那么怎么确定哪一个元素的优先级最高呢，jdk中使用堆这么一种数据结构，通过堆使得每次出队的元素总是队列里面最小的，而元素的大小比较方法可以由用户Comparator指定，这里就相当于指定优先级。java中几种常见的优先队列：PriorityQueue、PriorityBlockingQueue、DelayQueue、DelayedWorkQueue。

一、二叉堆基本原理

二叉堆的特点是：

• 完全二叉树
• 堆的根节点的优先级最大（即最大或最小）
• 父节点的优先级必定大于子节点，兄弟节点的优先级不确定谁大谁

时间复杂度插入O(log n)删除O(log n)构造O(n)

二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。说到二叉树我们就比较熟悉了，因为我们前面分析和学习过了二叉查找树和红黑树（TreeMap）。惯例，我们以最小堆为例，用图解来描述下什么是二叉堆。

上图就是一颗完全二叉树（二叉堆），我们可以看出什么特点吗，那就是在第n层深度被填满之前，不会开始填第n+1层深度，而且元素插入是从左往右填满。基于这个特点，二叉堆又可以用数组来表示而不是用链表，我们来看一下：

通过"用数组表示二叉堆"这张图，我们可以看出什么规律吗？那就是，基于数组实现的二叉堆，对于数组中任意位置的n上元素，其左孩子在[2n+1]位置上，右孩子[2(n+1)]位置，它的父亲则在[(n-1)/2]上，而根的位置则是[0]。

1.1  堆的构造过程

我们将上面我们图解中的数组去掉几个元素，只留下7、6、5、12、10、3、1、11、15、4（顺序已经随机打乱）。我们就按照当前的顺序建立一个二叉堆，暂时不用管它是否符合标准。

 

二、PriorityQueue的底层实现 2.1 PriorityQueue基本实现

我们看到PriorityQueue继承了AbstractQueue抽象类，并实现了Serializable接口，AbstractQueue抽象类实现了Queue接口，对其中方法进行了一些通用的封装。

public class PriorityQueue extends AbstractQueue
    implements java.io.Serializable {
}

// 默认初始化大小
privatestaticfinalintDEFAULT_INITIAL_CAPACITY = 11;


// 用数组实现的二叉堆，下面的英文注释确认了我们前面的说法。
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n